[백준] 13549: 숨바꼭질 3 - JAVA [자바]

안녕하세요.

오늘은 백준의 숨바꼭질 3 문제를 풀어보도록 하겠습니다.

 

 

 

📌 접근

최단 거리를 구해야하므로 bfs를 활용하였습니다.

또한 값을 늘리는 연산(+1, *2)는 100000을 넘지 않는 조건을,

값을 줄이는 연산(-1)은 0보다 작아지지 않는 조건을 걸어야합니다.

그래야 할당한 배열의 index를 넘는 오류가 발생하지 않습니다.

💻 풀이

import java.io.*;
import java.util.*;

// 최단 경로는 bfs로

public class Main {
    public static int N, K;
    public static int[] result = new int[100001];

    public static void bfs() {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(N);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int curSecond = result[cur];

            int a = cur * 2;
            int b = cur + 1;
            int c = cur - 1;

            if (a < 100001 && result[a] > curSecond) {
                result[a] = curSecond;
                queue.offer(a);
            }
            if (b < 100001 && result[b] > curSecond + 1) {
                result[b] = curSecond + 1;
                queue.offer(b);
            }
            if (c >= 0 && result[c] > curSecond + 1) {
                result[c] = curSecond + 1;
                queue.offer(c);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        Arrays.fill(result, Integer.MAX_VALUE);
        result[N] = 0;
        bfs();
        System.out.println(result[K]);
    }
}

🤔 고민했던 점 & 어려웠던 부분 

 

줄이는 연산을 할 때의 조건은, c > 0 이 아닌 c >= 0 이어야 한다.

c > 0 이라면 k = 0 일 때는 올바른 연산을 하지 못하기 때문이다.