[백준] 🥈 1697 숨바꼭질

📌 난이도

🥈 Silver 1

📌 문제

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

📌 풀이

처음 이 문제를 딱 보자 느낀 생각은 BFS랑 그 어떤 연관도 없어보이는데, 차라리 DP관련 문제가 아닌가? 하는 생각이었다.
왜냐하면 내가 지금까지 풀어본 DP문제에서 느낀 점은 바로 절대로 부분의 최적해가 전체의 최적해가 되지 않는다는 것이었다.

근데 가만히 생각해보니 DP와 BFS를 둘다 이미 지난 곳에 대한 정보를 그 위치에 저장하고, 다음에 그 정보를 이용하여 문제를 해결하는 되게 비슷한 알고리즘이라고 생각이 들었다.

그래서 sujin부터 시작하지만 모든 배열에 위치에 지금까지 걸린 시간을 넣어서 최종 sister의 위치에 도달한 시간을 출력하는 방법으로 구현을 하였다.

처음 BFS관련 문제를 해결하고 나서 다른 문제를 접하니까, 훨씬 쉽게 풀리는 느낌이 들었다.

📌 Code

package BFS;

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

public class N1697 {
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int subin = Integer.parseInt(st.nextToken());
        int sister = Integer.parseInt(st.nextToken());

        int max = 100000;
        arr = new int[max + 1];
        Arrays.fill(arr, -1);
        Queue<Integer> q = new LinkedList<>();

        arr[subin] = 0;
        q.add(subin);

        if ( subin == sister){
            System.out.println(0);
            return;
        }
        int cur;
        int nextPos;
        int time = 0;
        while (!q.isEmpty()) {
            cur = q.poll();
            nextPos = cur - 1;
            time = arr[cur] + 1;
            if (nextPos >= 0 && arr[nextPos] == -1) {
                arr[nextPos] = time;
                q.add(nextPos);
                if (nextPos == sister) {
                    System.out.println(time);
                    break;
                }
            }
            nextPos = cur + 1;
            if (nextPos <= max && arr[nextPos] == -1) {
                arr[nextPos] = time;
                q.add(nextPos);
                if (nextPos == sister) {
                    System.out.println(time);
                    break;
                }
            }
            nextPos = 2 * cur;
            if (nextPos <= max && arr[nextPos] == -1) {
                arr[nextPos] = time;
                q.add(nextPos);
                if (nextPos == sister) {
                    System.out.println(time);
                    break;
                }
            }
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁