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

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

13913번: 숨바꼭질 4

BFS를 사용하여 풀 수 있다.

 

핵심

시작점으로부터 +1,-1, *2 위치로 이동할 수 있다.

한번 방문한 곳은 이전에 방문했을 때가 최소이므로 재방문할 필요가 없다.

또한 이동경로를 구해야 하기 때문에 parent배열을 선언하여 이동 전 위치를 저장한다.

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int[] parent;
    static int[] time;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        if (n == k) {
            System.out.println(0);
            System.out.println(n);
        } else {
            bfs(n, k);
            System.out.println(time[k]-1);

            Stack<Integer> stack = new Stack<>();
            stack.push(k);
            int index = k;
            while (index!=n){
                stack.push(parent[index]);
                index = parent[index];
            }
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()){
                sb.append(stack.pop()).append(" ");
            }
            System.out.println(sb);
        }
    }

    public static void bfs(int n, int k) {
        Queue<Integer> q = new LinkedList<>();
        parent = new int[100001];
        time = new int[100001];
        q.offer(n);
        time[n] = 1;

        while (!q.isEmpty()) {
            Integer now = q.poll();

            if (now == k) return;

            if (now * 2 <= 100000 && time[now * 2] == 0) {
                time[now * 2] = time[now] + 1;
                parent[now * 2] = now;
                q.add(now * 2);
            }
            if (now + 1 <= 100000 && time[now + 1] == 0) {
                time[now + 1] = time[now] + 1;
                parent[now + 1] = now;
                q.add(now + 1);
            }
            if (now - 1 >= 0 && time[now - 1] == 0) {
                time[now - 1] = time[now] + 1;
                parent[now - 1] = now;
                q.add(now - 1);
            }
        }
    }
}

핵심

우선 n과 k가 같다면 굳이 bfs를 구하지 않아도 바로 값을 구할 수 있다.

만약 다르다면 bfs를 실행하게 된다.

재방문을 하지 않기 위해 time [x] == 0 일 경우에만 조건을 타도록 하였다.

time배열은 도달시간을 의미한다.

경로를 탐색하기 위해 k부터 다시 n으로 돌아가야 한다.

반대로 출력을 해야 하기 때문에 stack을 사용하였다.

 

 

배운 점

포스팅은 숨바꼭질 4만 하지만, 1부터 4까지 전부 풀어보았다.

서서히 어려워지며 내가 스스로 생각하지 못한 부분도 존재하였다.

하지만 충분히 생각한다면 할만한 문제라고 생각된다.

논리적으로 생각하며 영리하게 문제를 풀어야겠다.