[BOJ - JAVA] 13913 - 숨바꼭질 4 (BFS)

# 주소

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

13913번: 숨바꼭질 4

# 문제

# 문제 해설 및 코드리뷰

후 이거 풀다가 3시간동안 말도안되는 딜레마에 빠져서 사경을 헤맸습니다.

원래 코드가

import java.util.*;
public class Main{
    static int n,m;
    static int arr[] = new int[100001];
    static int ans[] = new int[100001];
    static int time = 0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        if(n == m){
        	System.out.println(0);
        else{
          Arrays.fill(arr, -1);
          bfs(n);
          System.out.println(arr[m]);
          Stack<Integer> stack = new Stack<>();
          int idx = m;
          while(idx != n){
              stack.push(idx);
              idx = ans[idx];
          }
        stack.push(idx);
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");

        }
        scan.close();
    }
    public static void bfs(int n){
        Queue<Integer> queue = new LinkedList<>();
        arr[n] = 0;
        queue.offer(n);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now * 2 < arr.length && arr[now * 2] == -1){
                arr[now * 2] = arr[now] + 1;
                queue.offer(now * 2);
                ans[now * 2] = now;
            }
            if (now + 1 < arr.length && arr[now + 1] == -1) {
                arr[now + 1] = arr[now] + 1;
                queue.offer(now + 1);
                ans[now + 1] = now;
            }
            if (now - 1 >= 0 && arr[now - 1] == -1) {
                arr[now - 1] = arr[now] + 1;
                queue.offer(now - 1);
                ans[now - 1] = now;
            }
            if(arr[m] != -1) {
                return;
            }
        }
    }
}

이거였는데 잘 보시면 n == m일 때 System.out.println(0)을 수행하고 끝이라고 작성했습니다.

근데 생각해보면 문제에서 시행 시간과 해당 배열 index를 출력해서 총 2줄이 되어야 하는데, 저는 단순이 n == m 일 때는 이동할 필요가 없으므로 0을 단독 출력해서 오답이 되는 것이었습니다.

분명 맞게 작성했는데 자꾸 73%에서 멈춰서 다른 분들꺼 보면서 뭐가 잘못됐는지 고치려고 코드를 수정하다보니 비슷하게 쓴 블로그가 되어버렸지만 원래 코드는 저기서 조금 다릅니다...

하지만 큰 틀은 같으니 그냥 이대로 정리하겠습니다.

 

위의 코드가 정답 코드입니다.

 

일단 arr와 ans를 100001크기로 선언합니다.

이후 arr를 -1로 채우고 bfs를 실행합니다.

이 bfs는 내부에서 Queue 자료구조를 사용했습니다.

bfs는 queue로 푸는 것이 원칙이기 때문에 Queue를 사용해야 합니다.

arr[n] (출발 지점) 은 0으로 선언하여 본격적으로 arr[n]의 크기를 1씩 늘려주는 방식을 채택했습니다.

따라서 queue에 n을 먼저 삽입하고 while문을 통해 queue를 가동합니다.

제일 먼저 now = queue.poll()로 꺼내온 뒤 이 now에 2배한 것, now에 +1한 것, now에 -1한 값이 arr.length보다 작고 0보다 크거나 같으며 방문하지 않은 arr 값 (boolean으로 해도 되지만 -1로 함)에 대해서 arr의 값을 1씩 증가시킵니다

이렇게 방문한 arr는 1씩 증가되기 때문에 다음에 방문할 때 들리지 않을 인덱스가 됩니다.

그리고 queue에도 증가된 now값을 각각 넣어주고 제일 중요한건 ans에도 now를 넣습니다.

이렇게 함으로써 우리가 구한 정답 bfs 인덱스에 어떤 now값이 들어갔는지 알 수 있습니다.

자 이를 통해 bfs문이 완전히 끝나면 Input 코드에 5 17이 입력되었을 때 4가 출력됩니다.

이 4는 5 -> 4 -> 8 -> 16 -> 17 이렇게 시행된다 할 때의 4라고 해봅시다.

다시 위로 올라가서 우리가 구한 arr[m]이 바로 4이므로 먼저 출력해주고 어떤 인덱스를 방문했는지 구하기 위해 Stack을 썼습니다.

저는 StringBuilder로 하려고 했는데 73%에서 막힐 때 다른 분들꺼 참고하면서 강제로 스택까지 쓰게 되었습니다.. ㅎㅎ

그러니 스택이 좀 더 고급져보이니 (사실 다시 고치기 귀찮음) 이걸 쓸게용

Stack 자료구조를 생성합니다.

그리고 while문을 통해 idx를 계속해서 stack에 넣습니다.

스택은 기본적으로 후입선출구조이기 때문에 마지막에 넣은 값이 제일 먼저 튀어나옵니다.

따라서 stack에 값을 넣을 때는 ans 배열에 넣은 now값들을 뒤에서부터 출력해주어야 합니다.

그러므로 stack에 idx를 차례대로 넣고 idx = ans[idx]함으로써 루프돌릴 때도 문제없습니다. (ans[17] = 16이므로 idx는 17 -> 16이 됩니다.)

이후 stack에는 17 16 8 4 가 삽입되고 마지막으로 현재 출발지점이었던 n또는 idx를 삽입하면 최종적으로 17 16 8 4 5가 삽입되고 stack.pop을 하여 제일 뒤에 있는 값부터 순서대로 출력하면 정답이 되겠습니다.

 

참 저도 바보인게.. 5 5를 입력값을 줄 생각을 왜 못했을까요.

생각해보면 5 5가 입력되면 당연히 0 5가 출력코드가 되어야 하는데 전 0만 보고 왜 아니지.. 이런 고민을 했으니까요.

이런걸 보고 등잔 밑이 어둡다고 하는가봐요.

감사합니다.