[BOJ] 1697번 : 숨바꼭질 (JAVA)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

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


public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[100001];
        Queue<Integer> queue = new LinkedList<>();

        queue.add(N);
        arr[N] = 1;

        while(!queue.isEmpty()){
            int tmp = queue.poll();
            if(tmp==K){
                System.out.print(arr[tmp]-1);
                break;
            }
            if(tmp-1>=0&&arr[tmp-1]==0){
                arr[tmp-1] = arr[tmp]+1;
                queue.add(tmp-1);
            }
            if(tmp+1<=100000&&arr[tmp+1]==0){
                arr[tmp+1] = arr[tmp]+1;
                queue.add(tmp+1);
            }
            if(2*tmp<=100000&&arr[2*tmp]==0){
                arr[2*tmp] = arr[tmp]+1;
                queue.add(2*tmp);
            }

        }

    }
}

N을 queue에 넣고 방문 배열 해당 인덱스에 1을 넣는다.

큐가 빌 때 까지 큐에 담긴 인덱스를 뽑으며 x-1, x+1, 2*x 값을 업데이트 한다. 이 때 방문 배열의 값이 0이 아니면 이미 방문했던 곳이기에 업데이트 하지 않는다.

큐에서 뽑은 인덱스가 K랑 같은 값이 되면 방문 배열의 값 -1을 한 값을 출력한다.

 

이런 유형의 bfs 문제는 처음이라 당황스러웠다. 이런 유형도 있구나 알 수 있는 문제였다.

방문 배열 선언 할 때 K+1로 했다가 런타임에러가 났었다. 생각해보니 N이 K보다 클 수도 있었고, 2*N이 K보다 클 수도 있었고 등등,, 안되는 이유는 많았다. 더 꼼꼼히 생각을 하는 연습을 해야겠다.