[백준/JAVA] 13913번: 숨바꼭질 4

🔺 문제

13913번: 숨바꼭질 4

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int[] time = new int[100001];    // location에 도착했을 때 시간
    static int[] parent = new int[100001];  // location으로 이동하기 직전 위치
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        BFS();
        
        // 순서대로 구하기 위해 스택에 넣었다가 pop
        Stack<Integer> stack = new Stack<>();
        stack.push(K);
        int idx = K;
        
        while(idx != N) {
            stack.push(parent[idx]);
            idx = parent[idx];
        }
        
        // 최종 출력
        sb.append(time[K] - 1 + "\n");
        
        while(!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }
        
        System.out.println(sb.toString());       
    }
    
    // BFS
    static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(N);
        time[N] = 1;    // 시작점 표시
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            if(now == K) return;
            
            for(int d = 0 ; d < 3 ; d++) {
                int next;
                
                if(d == 0)      next = now + 1;
                else if(d == 1) next = now - 1;
                else            next = now * 2;
                
                if(next < 0 || next > 100000) continue;
                
                if(time[next] == 0) {
                    queue.add(next);
                    time[next] = time[now] + 1;
                    parent[next] = now; // 자신의 부모 위치 = 직전 위치 기록
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ BFS + 스택
- time 배열 : 각 위치에 도달했을 때의 시간 저장
- parent 배열 : 이동 경로 저장 배열 (= 이동 직전 위치. 이)
- 출력 시, 스택과 parent 배열을 이용해 이동 경로 저장 후, 최종 도착지부터 시작점까지 거꾸로 올라가며 출력

 

💥 유의사항

• 62번째 줄, parent[next] = now ⇨ next로 이동하기 직전 위치를 저장.

 

---

🔺 다른 풀이들

- 설명 굿!!

[JAVA/백준] 13913번: 숨바꼭질 4

 

 

- 오 출력 방법이 신기하다.. StringBuider의 insert 메소드 사용하시고 스택은 사용 안 하심.

백준 - 13913 - 숨바꼭질4

---

💬 느낀 점

숨바꼭질 시리즈의 BFS 메소드에서 parent[next] = now; 이 한 줄만 추가되었다.

 

마지막에 출력 방법 아이디어만 떠올랐더라면..... 혼자 풀어서 맞았을터인데..

처음에 리스트 만들어서 출력해볼까..  싶었는데 모든 이동 경로가 다 나와가지고 당황했던...

 

담에는 옳은 방향으로 생각해서 더 잘해보는걸로!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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