21.07.07 - [BOJ] 1697. 숨바꼭질

[suhyunsim]

문제

• 숨바꼭질

핵심 아이디어

• BFS로 풀이
• 큐에 수빈이의 위치를 넣어가면서 이동시킨다
• 한 번 방문한 곳은 다시 방문하지 않는 것이 좋기 때문에, 따로 배열에 체크하면서 방문
• check[i] = i를 방문했는지
• dist[i] = i를 몇 번만에 방문했는지

어려운 점, 실수

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int MAX = 200000;
        Queue<Integer> queue = new LinkedList<>();
        int[] dist = new int[MAX];
        boolean[] check = new boolean[MAX];
        check[n] = true;
        dist[n] = 0;
        
        queue.offer(n);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now - 1 >= 0) {
                if(!check[now - 1]) {
                    queue.offer(now - 1);
                    check[now - 1] = true;
                    dist[now - 1] = dist[now] + 1;
                }
            }
            if (now + 1 < MAX) {                
                if (!check[now + 1]) {
                    queue.offer(now + 1);
                    check[now + 1] = true;
                    dist[now + 1] = dist[now] + 1;
                }
            }
            if (now * 2 < MAX) {
                if (!check[now * 2]) {
                    queue.offer(now * 2);
                    check[now * 2] = true;
                    dist[now * 2] = dist[now] + 1;                    
                }
            }
        }
        bw.write(String.valueOf(dist[k]));
        bw.flush();
        bw.close();
        br.close();
    }    
}