[BaekJoon] 12851번 - 숨바꼭질 2 [Java][C++]

문제 링크

---

1. 아이디어

BaekJoon 1697번 - 숨바꼭질 문제에서 최단 시간과 최단 시간에 찾는 경우의 수까지 구해야 하는 문제다. 수빈이가 각 좌표를 방문한 최단 시간을 저장하는 dist 배열을 활용해서 방문 체크겸 최단 시간 기록을 해줬고, 각 좌표를 방문한 횟수를 저장한 ways 배열을 활용해서 방문한 적이 없는 좌표면 이전 위치의 방문 횟수를 더해주고, 동일한 최단 시간에 방문할 수 있으면 해당 경우도 그 전 위치를 더해줘서 동일 시간 내에 갈 수 있는 경우의 수를 저장해줬다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static final int MX = 100_000;

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

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

        int[] res = bfs(n, k);
        System.out.println(res[0]);
        System.out.println(res[1]);
    }

    static int[] bfs(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(n);

        int[] dist = new int[1 + MX];
        Arrays.fill(dist, -1);
        dist[n] = 0;

        int[] ways = new int[1 + MX];
        ways[n] = 1;

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

            int nxt1 = cur - 1;
            if (nxt1 >= 0) {
                if (dist[nxt1] == -1) {
                    q.offer(nxt1);
                    dist[nxt1] = dist[cur] + 1;
                    ways[nxt1] = ways[cur];
                } else if (dist[nxt1] == dist[cur] + 1) {
                    ways[nxt1] += ways[cur];
                }
            }

            int nxt2 = cur + 1;
            if (nxt2 <= MX) {
                if (dist[nxt2] == -1) {
                    q.offer(nxt2);
                    dist[nxt2] = dist[cur] + 1;
                    ways[nxt2] = ways[cur];
                } else if (dist[nxt2] == dist[cur] + 1) {
                    ways[nxt2] += ways[cur];
                }
            }

            int nxt3 = cur * 2;
            if (nxt3 <= MX) {
                if (dist[nxt3] == -1) {
                    q.offer(nxt3);
                    dist[nxt3] = dist[cur] + 1;
                    ways[nxt3] = ways[cur];
                } else if (dist[nxt3] == dist[cur] + 1) {
                    ways[nxt3] += ways[cur];
                }
            }
        }

        return new int[]{dist[k], ways[k]};
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 100000;
int dist[1 + MX];
int ways[1 + MX];

void bfs(int n, int k) {
    queue<int> q;
    q.push(n);

    memset(dist, -1, sizeof(dist));
    dist[n] = 0;

    ways[n] = 1;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int nxt : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= nxt && nxt <= MX) {
                if (dist[nxt] == -1) {
                    q.push(nxt);
                    dist[nxt] = dist[cur] + 1;
                    ways[nxt] = ways[cur];
                } else if (dist[nxt] == dist[cur] + 1) {
                    ways[nxt] += ways[cur];
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    bfs(n, k);

    cout << dist[k] << '\n';
    cout << ways[k] << '\n';
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---