[백준] 13913번 숨바꼭질4 (Java)

백준 13913 숨바꼭질 4

DP와 BFS를 활용해야 한다는 것을 알아도 이것저것 실수해서 푸는데 시간이 걸린 문제다. target값을 찾은 후 비용을 출력하고 부모를 추적하며 찾아간다.

1. BFS 탐색이기 때문에 한 번 방문했던 노드를 다시 방문하는 것은 최솟값이 될 수 없다.
2. 이미 값이 target보다 크다면 2배를 곱하거나 1을 더할 필요가 없다.
3. K보다 N이 큰 경우, 값이 같아질 때까지 1을 빼야 한다.(메모리 초과 방지)

• 방문했는지 확인할 boolean 배열 isVisit
• 현재까지 비용을 저장할 int 배열 time
• 부모를 저장할 int 배열 parent

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        try {
            int n, m, tmp = 0;
            int [] time = new int[100001];
            int [] parent = new int[100001];
            boolean [] isVisit = new boolean [100001];
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            Queue <Integer> q = new LinkedList<>();
            ArrayList <Integer> al = new ArrayList<>();
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            q.add(n);
            isVisit[n] = true;

            // m이 n보다 작은 경우
            if (m < n){
                System.out.println(n - m);
                while(n >= m){
                    System.out.printf("%d ", n--);
                }
                System.exit(0);
            }

            // BFS
            while(!q.isEmpty()){
                tmp = q.poll();
                if(tmp == m){
                    System.out.println(time[tmp]);
                    break;
                } else{
                    if(tmp < m && tmp * 2 <= 100000 && !isVisit[tmp * 2]){
                        isVisit[tmp * 2] = true;
                        time[tmp * 2] = time[tmp] + 1;
                        parent[tmp * 2] = tmp;
                        q.add(tmp * 2);
                    }
                    if(tmp < m && tmp + 1 <= 100000 && !isVisit[tmp + 1]){
                        isVisit[tmp + 1] = true;
                        time[tmp + 1] = time[tmp] + 1;
                        parent[tmp + 1] = tmp;
                        q.add(tmp + 1);
                    }
                    if(tmp - 1 >= 0 && !isVisit[tmp - 1]){
                        isVisit[tmp - 1] = true;
                        time[tmp - 1] = time[tmp] + 1;
                        parent[tmp - 1] = tmp;
                        q.add(tmp - 1);
                    }
                }
            }
            // 출처 추적
            while(tmp != n){
                al.add(tmp);
                tmp = parent[tmp];
            }
            System.out.printf("%d ", n);
            for(int i = al.size() - 1; i >= 0; i --){
                System.out.printf("%d ", al.get(i));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}