[BFS] - G5_13549_숨바꼭질 3

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

13549번: 숨바꼭질 3

📌 - 처음 생각한 풀이

1. 방문 배열 -1로 초기화
2. 방문 배열이 -1이거나 BFS로 탐색했을 때 방문한 배열의 값이 이전 값보다 작으면 교체
3. BFS를 통해서 시작 숫자부터 목표 숫자까지 -1, +1 , *2 반복
4. 해당 번호에 도착하면 종료 및 출력

 

- 시간 복잡도는 따로 생각하지 않고 일단 로직이 맞는지 확인하고 싶어서 시간초과가 난다 생각하더라도 구현 함

- 제출했는데 계속 ArrayIndexOutOfBound가 발생해서 범위를 조정하고 수정했는데도 계속 발생해서 하다가 BFS로 푸는게 아니가 보다 하고 접었다가 다음날 다시 확인함

- 알고보니 뒤의 목표 숫자로만 배열을 만들다 보니 뒤의 목표 숫자가 앞의 시작 숫자 보다 낮을 경우 해당하는 배열만큼 초기화를 해주지 않아서 두 숫자 중 큰 값으로 배열을 초기화 함

->  로직은 맞았는데 스스로 믿지 못했기 때문에 틀렸다. 조금 더 확인을 했으면 아마 ArrayIndexOutOfBound 에러를 빠르게 해결했을텐데 그게 많이 아쉽다. 🥲

 

여러 문제를 풀다보니 이제 골드 5 정도의 BFS, DFS 문제는 무난하게 해결할 수 있을 것 같다는 자신이 든다. 앞으로 취직을 뽀개기 전까지 꾸준히 정진하자.

 

🔥 - Java 코드

 

package G5_13549_숨바꼭질3;

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

public class Main {
    public static int N, M, result = 0;
    public static int[] arr;

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int max = Math.max(N, M);
        arr = new int[(max + 1) * 2];

        Arrays.fill(arr, -1);
        BFS(N);


    }

    public static void BFS(int n) {
        Queue<Integer> queue = new LinkedList<>();

        arr[n] = 0;
        queue.add(n);

        while (!queue.isEmpty()) {
            int temp = queue.poll();
            if (temp == M) {
                System.out.println(arr[temp]);
                System.exit(0);
            }


            if (temp - 1 >= 0 && arr[temp - 1] == -1 || arr[temp - 1] > arr[temp] + 1) {
                arr[temp - 1] = arr[temp] + 1;
                queue.add(temp - 1);
            }


            if (temp + 1 < M * 2 && (arr[temp + 1] == -1 || arr[temp + 1] > arr[temp] + 1)) {
                arr[temp + 1] = arr[temp] + 1;
                queue.add(temp + 1);
            }
            if (temp * 2 < M * 2 && (arr[temp * 2] == -1 || arr[temp * 2] > arr[temp])) {
                arr[temp * 2] = arr[temp];
                queue.add(temp * 2);
            }


        }


    }


}