백준 12851 자바 - 숨바꼭질 2 문제

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

이 문제는 앞서 풀었던 숨바곡질 문제 - wellbell.tistory.com/64

에서 동일 시간에 대한 중복을 체크하지않는 형태라고 보면된다.

중복은 현재에 대한 것만 중복체크를 하고 next에 관련해서 중복을 체크하지않고 count를 세는 방식인것이다.

현재에 대한 것을 중복 체크하는 이유는 현재를 체크할때 보다 뒤에 나오는 것들은 최소 시간보다 무조건 높기 때문이다. 

bfs 메서드의 while문을 빠저나오는 조건또한 이전 방문 여부에서 count가 세어진 경우로 변경한다.

count가 세어졌다는 의미는 만난 경우를 카운트 했다는 의미이기 때문이다.

 

 

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

// 숨바꼭질2 문제 - 12851번
public class HideAndSeek2 {

    static int N, K;
    static boolean[] visited = new boolean[100001];
    static int time = 0;
    static int count = 0;

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // 두 사람이 같은 장소에 있는 경우
        if(N == K){
            System.out.println(0);
            System.out.println(1);
        }else {
            bfs(N);
            System.out.println(time);
            System.out.println(count);
        }
    }

    static void bfs(int start) {
        time = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        while (!q.isEmpty()) {
            // 만나 경우가 1번이라도 있으면 다음 계산부터는 최소가 아님
            if(count != 0) {
                return;
            }

            // 현재 q의 사이즈 만큼만 돌리기 - 시간 계산을 위해서
            for(int j = 0, size = q.size(); j < size; j++) {
                int now = q.poll();
                // 현재 방문 처리 - 현재를 방문한 시점 이후로 나오는 모든 방문은 중복처리
                visited[now] = true;
                int next;

                // 다음에서 만나는 경우 count + 1
                // 다음에서 못 만나는 경우 큐에 추가
                next = now - 1;
                if(next == K) {
                    count++;
                } else if(next >= 0 && !visited[next]) {
                    q.offer(next);
                }

                next = now + 1;
                if(next == K) {
                    count++;
                } else if(next < 100001 && !visited[next]) {
                    q.offer(next);
                }

                next = now * 2;
                if(next == K) {
                    count++;
                } else if(next < 100001 && !visited[next]) {
                    q.offer(next);
                }
            }
            time++;
        }
    }
}