백준 - 12851 - 숨바꼭질2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
/**
 * 백준 - 12851
 */
public class 숨바꼭질2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split(" ");
        Integer N = Integer.valueOf(inputs[0]);
        Integer K = Integer.valueOf(inputs[1]);
 
        if(N >= K) {
            System.out.println(N-K);
            System.out.println(1);
            return;
        }
 
        bfs(N, K);
    }
 
    private static void bfs(Integer N, Integer K) {
        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        int[] dist = new int[100001];
        Arrays.fill(dist, -1);
 
        q.offer(N);
        dist[N] = 0;
 
        while (!q.isEmpty()) {
            Integer curNode = q.poll();
 
            if(dist[K] != -1 && dist[K] < dist[curNode]) {
                break;
            }
 
            int[] nextPos = new int[]{curNode-1, curNode+1, curNode*2};
            for(int i=0; i<nextPos.length; i++) {
                Integer nextNode = nextPos[i];
 
                if(nextNode < 0 || nextNode > 100000) continue;
 
                if(dist[nextNode] == -1 || dist[nextNode] == dist[curNode] + 1) {
                    q.offer(nextNode);
                    dist[nextNode] = dist[curNode] + 1;
 
                    if(nextNode.equals(K)) {
                        count++;
                    }
                }
            }
        }
 
        System.out.println(dist[K]);
        System.out.println(count);
    }
}
 

알고리즘

• BFS
• 트리의 특정 높이에 있는 노드들 중에 특정 노드의 수를 구하는 문제.
• BFS의 흐름이 머리속에 그려져야 풀수있다.
• BFS는 루트 노드부터 시작해서 자식을 순차적으로(너비우선탐색) 탐색한다.
• 따라서 최단 거리의 경우부터 탐색되며, 같은 높이의 특정 노드를 탐색하기 위해서는 중복을 허용해야한다.
• 단, 모든 중복을 허용할 경우,, 답이 안나온다..방문했던 곳을 또 방문하면 끝이 없기 때문이다..
• 중복을 허용하는 기준은
• 방문하지 않았거나(dist[nextNode] == -1)
• 방문했지만 방문했던 곳이 다음 노드의 형제이면 중복을 허용해준다. (dist[nextNode] == dist[curNode] + 1)
• 또한 해당 높이를 모두 탐색한 후에는 그 다음 높이의 탐색은 불필요하므로 생략한다 (if(dist[K] != -1 && dist[K] < dist[curNode]) break;
• 또 주의해야할 점은 N이 K보다 크거나 같은 경우 -1하면서 계속 뒤로 가는 수밖에 없기 때문에 BFS가 아닌 예외적으로 따로 처리해 주어야한다.