[java]숨바꼭질 2 - 백준12851

문제

• 숨바꼭질 2(백준12851)

풀이

문제 해석을 하자면,

• 숨바꼭질 문제는 시리즈로 여러개 존재한다.
• 1~4 까지 풀어봤고 이 문제만 정리하고자 한다. -> visited 사용시점 확인이 목표!

풀이

• DP도 가능하고 BFS도 가능하다. BFS가 더 간단하다.
  • 한번 움직일 때 1초이며 최소 시간이니 BFS 적합 (최단거리)
• BFS 일반 로직을 사용하면 바로 구할 수 있는데, visited 를 갱신하는 시점이 중요하다.
• 본인이 생각하는 갱신 시점은 2가지 이다.
  • qu.poll() 사용하는 그 시점에 visited = true 하느냐
  • next 값 구해서 큐에 삽입하는 그 시점에 visited = true 하느냐
• 본인은 보통 “큐에 삽입 시점” 에 갱신하지만, 이 문제에서는 “qu.poll()” 시점에 사용하자!
  • 만일 “큐 삽입 시점” 에 갱신하면 여러 예외처리 할 것이 생기게 됨.

코드

static int N, K;
static int result, result2; // 동생 찾는 시간, 동생 찾는 방법 수
static boolean[] visited;

static void check(int cur, Deque<Integer> qu) {
    // 3가지 연산 경우로 가지치기
    if(cur+1 <= K+1 && !visited[cur+1]) { // cur+1 범위 방지 필수
        qu.offer(cur + 1);
    }
    if(cur*2 <= K*2 && !visited[cur*2]) { // cur*2 범위 방지 필수
        qu.offer(cur * 2);
    }
    if(cur-1 >= 0 && !visited[cur-1]) { // cur-1 음수 방지 필수
        qu.offer(cur - 1);
    }
}

static void bfs(){
    Deque<Integer> qu = new ArrayDeque<>();
    qu.offer(N);
    visited[N] = true;
    boolean endPoint = false; // 종료시점 기록
    while(!qu.isEmpty()) {
        if(endPoint) return;
        int size = qu.size();
        result++;
        for (int s = 0; s < size; s++) {
            int cur = qu.poll();
            if(cur==K) {
                result2++;
                endPoint=true; // 해당 큐 과정 끝나면 종료할 목적
                continue;
            }
            visited[cur] = true;
            check(cur, qu);
        }
    }

}

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());
    visited = new boolean[300005]; // 2X 연산 때문에 크기 넉넉히 잡았음
    //run
    bfs();
    //output
    System.out.println(result-1);
    System.out.println(result2);
}

느낀점

생략