[Java] 백준 12851번 : 숨바꼭질 2*

문제

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

12851번: 숨바꼭질 2

 

 

풀이 과정

BFS를 떠올리기는 쉬웠는데 K까지 도달하는 개수를 어떻게 셀 지에 대해서 생각하기가 어려웠다.

방문체크를 q에서 꺼낼 때함으로써, 현재 step에서는 중복을 허용하되 다음 step에서는 이전에 방문한 것을 제외하고 방문하도록 할 수 있었다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[100001];
        Queue<Integer> q = new LinkedList<>();
        q.add(N);

        int step = 0, cnt = 0;
        while(!q.isEmpty()){
            for(int i=0, size = q.size(); i<size; i++){
                int now = q.poll();
                visited[now] = true;
                if(now == K){
                    cnt++;
                    continue;
                }
                if(now > 0 && !visited[now - 1]){
                    q.add(now - 1);
                }
                if(now + 1 <= 100_000 && !visited[now + 1]){
                    q.add(now + 1);
                }
                if(now * 2 <= 100_000 && !visited[now * 2]){
                    q.add(now * 2);
                }
            }
            if(cnt > 0) break;
            step++;
        }

        StringBuilder sb = new StringBuilder();
        sb.append(step).append("\n").append(cnt);
        System.out.println(sb);
    }
}

 

 

결과