[백준] 13913 숨바꼭질 4

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

13913번: 숨바꼭질 4

2021-07-09

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main13913 {
    public static int N, K;
    public static int[] dir = {-1, 1, 2};
    public static boolean[] vtd;
    public static int[] arr;
    public static Queue<Integer> q;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        vtd = new boolean[100001];
        arr = new int[100001];
        q = new LinkedList<>();
        q.add(N);
        vtd[N] = true;
        int count = 0;
        Stack<Integer> s = new Stack<>();
        StringBuilder sb = new StringBuilder();
 
        if(N == K) {
            sb.append(N);
        } else {
            loop:while(!q.isEmpty()) {
                int size = q.size();
                while(size > 0) {
                    int xx = q.poll();
 
                    int nx = 0;
                    for(int i = 0; i < 3; i++) {
                        if(i == 2) {
                            nx = xx * dir[i];
                        } else {
                            nx = xx + dir[i];
                        }
 
                        if(nx < 0 || nx > 100000 || vtd[nx]) continue;
 
                        arr[nx] = xx;
                        if(nx == K) {
                            count++;
                            int start = nx;
                            s.push(nx);
                            while(start != N) {
                                s.push(arr[start]);
                                start = arr[start];
                            }
                            break loop;
                        }
                        vtd[nx] = true;
                        q.add(nx);
                    }
                    size--;
                }
                count++;
            }
        }
 
        while(!s.isEmpty()) {
            sb.append(s.pop()).append(" ");
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }
}
 

#문제풀이

 

BFS문제이다.

 

1) 처음에 List를 들고다니면서, 경로를 저장해줬었는데 시간초과가 났다. 

 

2) 두번째는 현재 시점의 바로 앞 경로만 따로 저장을 해주고, 마지막에 그 경로들을 다시 재탐색하면서 stringbuilder에 저장해줬다. 뒤집어서 해야해서,, insert를 썼었다. 그런데 여기서도 시간초과가 났었다. 

sb.append(nx);
while(start != N) {
   sb.insert(0, arr[start]).insert(String.valueOf(arr[start]).length(), " ");
   start = arr[start];
}

 

3) 그래서 결국 경로 재탐색하면서 stack에 저장하고, 마지막으로 stack에 있는것들 pop하면서 stringbuilder에 append 하는 방식으로 처리했다.