백준 실버1 숨바꼭질 1697 자바

🧫 문제 분석

✔️ 출처

숨바꼭질 1697번 - 백준

📖 문제

---

🔅 문제 풀이

수빈이의 위치 x
동생의 위치 k

수빈이는 -1, +1, *2 로 이동할 수 있고 이는 1초를 사용한다.

graph를 조건에 만족하는 최대 크기로 만들어서 각 위치에 따른 초를 적을 것이다.
처음 수빈이가 있는 장소는 1로 초기화한다.

너비우선탐색으로 하되 문제에서 주어진 위치에 대한 조건식을 걸어주고 (0 <= x, k <= 100000)
이동하려는 곳에 이전에 이동한 흔적이 있는지 확인하여 걸린시간이 덮어씌어지는 것을 방지한다.

x-1, x+1, x*2 3번의 위치이동을 하고 graph 인덱스의 값에 현재 위치의 걸린시간 +1 초를 더해 이동한 흔적을 남긴다. 그리고 이동한 위치를 queue에 넣는다. 방문하지 않은 곳은 걸린시간이 0이다. 왜냐하면 graph를 만들 때 수빈이의 위치말곤 따로 값을 초기화해주지 않았기 때문이다.
루프를 돌면서 queue에서 꺼낸 위치가 동생 위치일 때, 수빈이가 동생에게 도달했다는 것이고,
그 위치에는 분명 이동한 흔적이 있을 것이다. 그것이 가장 빨리 도달한 시간이다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int answer;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] graph = new int[100001];

        int x = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());


        graph[x] = 1;

        bfs(x, graph, k);
        bw.write(answer+"\n");
        bw.flush();
        bw.close();

    }

    private static void bfs(int x, int[] graph, int k) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);

        while (!q.isEmpty()) {
            int current = q.poll();
            int count = graph[current];

            if (current == k) {
                answer = count - 1;
                return;
            }

            if (current - 1 >= 0 && graph[current - 1] == 0) {
                graph[current - 1] = count + 1;
                q.add(current - 1);
            }
            if (current + 1 < graph.length && graph[current + 1] == 0) {
                graph[current + 1] = count + 1;
                q.add(current + 1);
            }
            if (current * 2 < graph.length && graph[current * 2] == 0) {
                graph[current * 2] = count + 1;
                q.add(current * 2);
            }
        }

    }
}

이런 문제 잘 못풀어서 힘들었다.

❗ 오답노트 / 필요한 지식

bfs, dfs 에 대한 특징에 대해 아직은 학습이 부족한 것 같다. 더 공부해야한다.