[백준 / Java] 13913: 숨바꼭질 4 (BFS)

난이도: Gold 4

문제: https://www.acmicpc.net/problem/13913

 

아래 링크에 있는 문제를 응용한 문제이다.

이 문제를 먼저 풀어보고 해당 문제를 풀면 좀 더 쉽게 풀 수 있을 것이다.

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

 

<문제>

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

---

 

수빈이가 있는 위치 N은 5, 동생이 있는 위치는 17이라고 해보자.

 

수빈이가 있는 위치(N)에서 -1, +1, *2한 값들을 자식 노드로 삽입한다.

즉, 5의 자식 노드들은 4, 6, 10이다.

 

그리고 그 자식 노드들에서도 각각 -1, +1, *2한 값들을 자식 노드로 삽입한다.

즉,

4의 자식 노드들은 3, 5, 8

6의 자식 노드들은 5, 7, 12

10의 자식 노드들은 9, 11, 20

 

이런 식으로 계속 자식 노드들은 만들어가다가,

위치가 K인 자식 노드를 찾으면 해당 노드의 트리 깊이가 바로 수빈이가 동생을 찾는 가장 빠른 시간이 된다.

 

위치가 K인 자식 노드를 찾을 때까지의 트리는 다음과 같이 구성된다.

 

 

K가 17이므로, 17을 찾을 때까지만 그렸다. 그 외의 경로는 필요가 없기에 생략했다.

루트 노드의 깊이는 0이고, 17인 노드의 깊이는 4이다.

참고로 깊이는 다음과 같다.

 

 

경로를 저장하려면 17인 노드의 부모 노드들의 정보도 모두 알아야 한다.

그렇다면 우리에게 필요한 것은 현재 노드의 위치, 현재 노드의 깊이, 부모 노드 객체이다.

현재 노드의 위치, 현재 노드의 깊이, 부모 노드 객체를 저장하는 클래스를 만들자.

 

 

    static class Node {

        int num;        // 현재 위치

        int depth;      // 그래프(트리)의 깊이

        Node parent;    // 부모 노드

       

        Node(int num, int depth, Node parent) {

            this.num = num;

            this.depth = depth;

            this.parent = parent;

        }

    }

 

 

K인 노드를 먼저 스택에 삽입하고, 부모 노드들을 차례로 뽑아서 스택에 삽입하면 경로를 저장할 수 있다.

 

 

주석에 설명을 한 줄 한 줄 자세히 적어놓았다.

자, 그럼 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class P13913_숨바꼭질4 {
    static int N;                        // 수빈이가 있는 위치
    static int K;                        // 동생이 있는 위치
    static ArrayList<Node>[] graph;        // bfs 수행을 위한 ArrayList 배열 그래프
    static Stack<Node> position = new Stack<>();    // 이동 경로를 저장하는 스택
    
    static class Node {
        int num;        // 현재 위치
        int depth;        // 그래프(트리)의 깊이
        Node parent;    // 부모 노드
        
        Node(int num, int depth, Node parent) {
            this.num = num;
            this.depth = depth;
            this.parent = parent;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());    
        graph = new ArrayList[100001];
        
        // 그래프 초기화
        for (int i = 0; i <= 100000; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // bfs 수행 중 노드의 현재 위치(num)가 동생이 있는 위치(K)와 같으면, 
        // 이동 위치 저장 스택(position) 스택에 그 노드를 삽입 후
        // 수빈이가 동생을 찾는 가장 빠른 시간 리턴
        int minTime = bfs();    
        
        Node node = position.pop();    // 현재 위치(num)가 동생의 위치(K)인 노드 (반복자로 사용)
        
        while (true) {
            position.push(node);    // 현재 노드를 이동 경로 저장 스택(position)에 삽입
            if (node.parent == null) {    // 현재 노드의 부모 노드가 null이라면
                break;                    // 현재 노드를 출발 노드(루트 노드)까지 탐색을 했으므로 반복문 탈출
            }
            node = node.parent;        // 현재 노드를 부모 노드로 변경
        }
        
        bw.write(minTime + "\n");    // 수빈이가 동생을 찾는 가장 빠른 시간 출력
        
        // 이동 경로 저장 스택이 빌 때까지 반복
        while (!position.isEmpty()) {    
            node = position.pop();        // 이동 경로 저장 스택에서 노드 뽑기
            bw.write(node.num + " ");    // 노드의 현재 위치를 출력
        }
        
        bw.flush();        // bw.write()로 버퍼에 쌓았던 문자열들을 한 번에 쓰기 => 속도 더 빠름
    }
    
    public static int bfs() {
        Queue<Node> queue = new LinkedList<>();        // bfs 수행을 위한 큐
        boolean[] visited = new boolean[100001];    // bfs 수행을 위한 방문 배열
        
        // 출발 노드(루트 노드) 생성
        // now(현재 위치): N
        // depth(그래프(트리)의 깊이): 루트 노드는 0
        // parent(부모 노드): 루트 노드는 부모 노드가 없으므로 null
        Node node = new Node(N, 0, null);    
        queue.add(node);                    // 큐에 루트 노드 삽입
        visited[N] = true;                    // 루트 노드의 현재 위치를 방문 체크
        addGraph(node);                        // 루트 노드의 자식 노드들 생성하고 연결 
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Node now = queue.poll();    // 큐에서 현재 노드 뽑기
            
            if (now.num == K) {            // 현재 노드의 위치가 동생의 위치와 같다면
                position.push(now);        // 이동 경로 저장 스택에 현재 노드 삽입
                return now.depth;        // 현재 노드의 깊이(= 수빈이가 동생을 찾는 가장 빠른 시간) 리턴
            }
            
            // 현재 노드의 자식 노드들 탐색
            for (Node next : graph[now.num]) {            
                if (!visited[next.num]) {    // 자식 노드의 현재 위치를 방문하지 않았다면
                    queue.add(next);        // 큐에 자식 노드 삽입
                    visited[next.num] = true;    // 자식 노드의 현재 위치를 방문 체크
                    addGraph(next);                // 자식 노드의 자식 노드들 생성하고 연결
                }
            }
        }
        
        return -1;
    }
    
    // 노드의 자식 노드들을 생성하고 연결하는 메서드
    public static void addGraph(Node head) {
        // 현재 노드의 위치에서 1을 뺀 값이 0 이상이라면 (인덱스가 유효 범위라면)
        if (head.num - 1 >= 0) {
            // 자식 노드 생성
            // now(현재 위치): 현재 노드의 위치 - 1 
            // depth(그래프(트리)의 깊이): 현재 노드의 깊이 + 1
            // parent(부모 노드): 현재 노드
            Node tail = new Node(head.num - 1, head.depth + 1, head);
            graph[head.num].add(tail);    // 현재 노드에 자식 노드 연결
        }
        // 현재 노드의 위치에서 1을 더한 값이 100000 이하라면 (인덱스가 유효 범위라면)
        if (head.num + 1 <= 100000) {
            // 자식 노드 생성
            // now(현재 위치): 현재 노드의 위치 + 1 
            // depth(그래프(트리)의 깊이): 현재 노드의 깊이 + 1
            // parent(부모 노드): 현재 노드
            Node tail = new Node(head.num + 1, head.depth + 1, head);
            graph[head.num].add(tail);    // 현재 노드에 자식 노드 연결
        }
        // 현재 노드의 위치에서 2를 곱한 값이 100000 이하라면 (인덱스가 유효 범위라면)
        if (head.num * 2 <= 100000) {
            // 자식 노드 생성
            // now(현재 위치): 현재 노드의 위치 * 2
            // depth(그래프(트리)의 깊이): 현재 노드의 깊이 + 1
            // parent(부모 노드): 현재 노드
            Node tail = new Node(head.num * 2, head.depth + 1, head);
            graph[head.num].add(tail);    // 현재 노드에 자식 노드 연결
        }
    }
}