백준 - 13913 - 숨바꼭질4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

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

알고리즘

• BFS
• 숨바꼭질1,2에 비해 4는 경로까지 출력해야하는 문제이다.
• 경로를 출력하기 위해선, 노드의 부모는 오직 하나만 존재하는 것을 이용해 부모를 배열에 저장해하고 목적지 부터 루트노드까지 역으로 출력한다.
• 주의할 점은 String으로 연산할 경우 객체를 새로 생성하는데 비용이 많이 들기 때문에 시간초가가 나온다(테스트: 100000 0)
• 그래서 String말고 StringBuilder를 이용하여 연산하도록 하자.