[백준] BOJ_12851 숨바꼭질 2

1.문제 요약

• 동생을 찾는 최단 시간과 그 방법의 수를 구하는 문제
• 찾는 방법은 3가지 행동 중 하나를 선택할 수 있다
  - X - 1 위치로 이동
  - X + 1 위치로 이동
  - X * 2 위치로 이동

2.접근 방식

• BFS 알고리즘: 처음 찾았을 때 최단 시간임을 보장할 수 있어서 사용
• 중복 방문 처리
• 경로 개수 누적 카운팅

3. 시도했지만 실패한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int K;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int answer = Integer.MAX_VALUE;
        int count = 0;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(N, 0));

        while (!q.isEmpty()) {
            Node now = q.poll();
            if (now.idx == K && now.time <= answer) {
                answer = now.time;
                count += 1;
                continue;
            }

            if (now.time < answer) {
                q.add(new Node(now.idx * 2, now.time + 1));
                q.add(new Node(now.idx + 1, now.time + 1));
                q.add(new Node(now.idx - 1, now.time + 1));
            }
        }

        System.out.println(answer);
        System.out.println(count);
    }

    static class Node {
        int idx;
        int time;

        public Node(int i, int t) {
            this.idx = i;
            this.time = t;
        }
    }
}

최단 시간임을 보장할 수 있는 BFS 알고리즘을 사용했지만 메모리 초과라는 결과가 나왔습니다. 이유는 같은 위치를 불필요하게 다시 탐색하는 것을 막지 못했기 때문...

4.최종 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int K;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println(N - K);
            System.out.println(1);
            return;
        }

        Queue<Integer> q = new LinkedList<>();
        q.add(N);

        int[] time = new int[100_001];
        int[] cnt = new int[100_001];

        time[N] = 1;
        cnt[N] = 1;

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

            for (int next : getNext(now)) {
                if (0 <= next && next <= 100_000) {
                    if (time[next] == 0) {
                        q.add(next);
                        time[next] = time[now] + 1;
                        cnt[next] = cnt[now];
                    } else if (time[next] == time[now] + 1) {
                        cnt[next] += cnt[now];
                    }
                }
            }
        }

        System.out.println(time[K] - 1);
        System.out.println(cnt[K]);
    }

    private static int[] getNext(int idx) {
        return new int[]{idx - 1, idx + 1, idx * 2};
    }
}

최단 시간을 기록하는 배열과 방문 회수를 기록하는 배열이 필요하다는 것을 몸소 깨우치고 코드를 수정했습니다.

5.회고

• 배운점: 이 문제를 풀면서 일반적인 BFS 문제와 다르게 중복 방문을 조건부로 허용해야 한다는 점을 배웠습니다. 단순히 최단 거리만 구하는 것이 아니라 최단 거리로 도달하는 경로의 개수까지 구해야 하므로, 방문 처리 로직을 세밀하게 조정해야 했습니다.
• 자료구조: Queue
• 알고리즘: BFS, 조건부 중복 방문 처리
• 주의사항: N >= K 경우 뒤로가는 방법 별도 처리