[백준] 12851 숨바꼭질 2

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

12851번: 숨바꼭질 2

2021-06-27

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main12851 {
    public static int N, K;
    public static int[] dir = {2, -1, 1};
    public static boolean[] vtd;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        vtd = new boolean[100001];
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        vtd[N] = true;
 
        int time = 0;
        int count = 0;
        if(N == K) {
            count = 1;
        } else {
            while(!q.isEmpty()) {
                int size = q.size();
                count = 0;
                boolean flag = false;
                while(size > 0) {
                    int x = q.poll();
                    vtd[x] = true;
                    int nx = 0;
                    for(int i = 0; i < dir.length; i++) {
                        if(i == 0) {
                            nx = x * dir[i];
                        } else {
                            nx = x + dir[i];
                        }
                        if(nx < 0 || nx > 100000) continue;
                        if(nx == K) {
                            flag = true;
                            count++;
                        }
                       if(!vtd[nx]) {
                            q.add(nx);
                        }
                    }
                    size--;
                }
                time++;
                if(flag) break;
            }
        }
 
        System.out.println(time);
        System.out.println(count);
    }
}

 

#문제풀이

몇 달만이지;; 

 

보통의 bfs 문제를 풀때는 queue에 push 하기 전에 visit 체크를 했었다.

하지만 이 문제 같은 경우에는 push 할 때는 경우의 수가 겹칠 수가 있어서, pop 시점에서 visit 체크를 해줬어야 했다.

 

예시) 1 3 일 경우, 2 2 가 답으로 나와야한다.