[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 MAX = 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[] result = bfs(n, k);
        System.out.println(result[0]);
        System.out.println(result[1]);
    }

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

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

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

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

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

            int next2 = node + 1;
            if (next2 <= MAX) {
                if (dist[next2] == -1) {
                    q.offer(next2);
                    dist[next2] = dist[node] + 1;
                    ways[next2] = ways[node];
                } else if (dist[next2] == dist[node] + 1) {
                    ways[next2] += ways[node];
                }
            }

            int next3 = node * 2;
            if (next3 <= MAX) {
                if (dist[next3] == -1) {
                    q.offer(next3);
                    dist[next3] = dist[node] + 1;
                    ways[next3] = ways[node];
                } else if (dist[next3] == dist[node] + 1) {
                    ways[next3] += ways[node];
                }
            }
        }

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

2. 풀이 [C++]

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

constexpr int MAX = 100000;
int dist[1 + MAX];
int ways[1 + MAX];

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

    fill(dist, dist + MAX + 1, -1);
    dist[n] = 0;

    ways[n] = 1;

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

        int next1 = node - 1;
        if (next1 >= 0) {
            if (dist[next1] == -1) {
                q.push(next1);
                dist[next1] = dist[node] + 1;
                ways[next1] = ways[node];
            } else if (dist[next1] == dist[node] + 1) {
                ways[next1] += ways[node];
            }
        }

        int next2 = node + 1;
        if (next2 <= MAX) {
            if (dist[next2] == -1) {
                q.push(next2);
                dist[next2] = dist[node] + 1;
                ways[next2] = ways[node];
            } else if (dist[next2] == dist[node] + 1) {
                ways[next2] += ways[node];
            }
        }

        int next3 = node * 2;
        if (next3 <= MAX) {
            if (dist[next3] == -1) {
                q.push(next3);
                dist[next3] = dist[node] + 1;
                ways[next3] = ways[node];
            } else if (dist[next3] == dist[node] + 1) {
                ways[next3] += ways[node];
            }
        }
    }
}

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

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

    bfs(n, k);

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

---