(Java) 백준 1697 - 숨바꼭질

가장 빠른 시간이라는 문장에서 BFS를 사용해야겠다는 생각을 했다.

다만 어떤 식으로 BFS를 사용해야 하는지 모르겠어서 검색을 통해 다른 분들 답안을 참고했다.

visited 배열을 사용해서 방문처리와 이동 횟수를 카운팅 하는 방법을 사용해서 풀었다.

어려운 문제라는 생각은 안들었지만 BFS에 아직도 익숙하지 않은 것 같아 계속 연습해야 할 것 같다.

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m, cnt;
    static int[] visited = new int[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        bfs(n);
        System.out.println(cnt);
    }

    static void bfs(int num) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(num);
        // n값 방문 처리
        visited[num] = 1;
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            // n이 m과 같아지면
            if(temp == m) {
                cnt = visited[temp] - 1; return;
            }
            // 범위를 벗어나지 않고 방문한적이 없다면
            if (temp - 1 >= 0 && visited[temp - 1] == 0) {
                visited[temp - 1] = visited[temp] + 1;
                queue.offer(temp - 1);
            }
            if (temp + 1 <= 100000 && visited[temp + 1] == 0) {
                visited[temp + 1] = visited[temp] + 1;
                queue.offer(temp + 1);
            }
            if (temp * 2 <= 100000 && visited[temp * 2] == 0) {
                visited[temp * 2] = visited[temp] + 1;
                queue.offer(temp * 2);
            }
        }
    }
}