이번에는 백준 12851번 숨바꼭질 2 문제를 풀어보았습니다.
처음에는 DFS를 이용하여 모든 이동 경로를 탐색하는 방식으로 구현해보았습니다.
이동 가능한 경우가 -1, +1, *2 세 가지이기 때문에 모든 경우를 탐색하면서 최단 시간과 경우의 수를 계산하도록 하였습니다.
하지만 이 문제는 최단 시간과 그 최단 시간으로 도달하는 경우의 수를 구해야 하는 문제였습니다.
이후에는 BFS를 이용하여 최단 시간을 구하고, 같은 최단 시간으로 도달하는 경우의 수를 함께 저장하는 방식으로 다시 구현하였습니다.
문제 설명
수빈이는 현재 위치 N에 있고, 동생은 K에 있습니다.
수빈이는 다음 세 가지 방법으로 이동할 수 있습니다.
- X - 1
- X + 1
- X * 2
수빈이가 동생을 찾을 수 있는 가장 빠른 시간과, 그 시간으로 도달하는 방법의 수를 구하는 문제입니다.
풀이 아이디어
V1
DFS를 이용하여 가능한 모든 이동 경로를 탐색하였습니다.
현재 위치에서 -1, +1, *2 위치로 이동하도록 구현하였고, 이미 현재 경로에서 방문한 위치는 다시 방문하지 않도록 처리하였습니다.
동생을 찾은 경우 현재 최단 시간과 비교하여 값을 갱신하였습니다.
V2
최단 시간을 구하는 문제이기 때문에 BFS를 사용하는 것이 더 적절하다고 생각했습니다.
BFS를 수행하면서 visited 배열에는 해당 위치까지 도달하는 최단 시간을 저장하였습니다.
또한 cnt 배열에는 해당 위치까지 최단 시간으로 도달하는 경우의 수를 저장하였습니다.
같은 최단 시간으로 다시 방문한 경우에는 경우의 수를 누적하도록 구현하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int brother, subin;
int ret = INT_MAX;
int ret_cnt;
int visited[100001];
void solve(int idx, int level) {
if (idx > 100000 || idx < 0) {
return;
}
if (visited[idx]) return;
if (level > ret) return;
if (level == ret && idx == brother) {
ret_cnt++;
return;
}
if (idx == brother && level < ret) {
ret = level;
ret_cnt = 1;
return;
}
visited[idx] = 1;
for (int i = 1; i <= 3; i++) {
if (i == 1) {
solve(idx-1, level+1);
}
else if (i == 2) {
solve(idx+1, level+1);
}
else if (i == 3) {
solve(idx*2, level+1);
}
}
visited[idx] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> subin >> brother;
solve(subin, 0);
cout << ret << '\n' << ret_cnt << '\n';
return 0;
}V1 풀이 흐름
- 현재 위치에서 이동 가능한 세 방향을 탐색합니다.
- 현재 경로에서 이미 방문한 위치는 다시 방문하지 않습니다.
- 범위를 벗어나는 경우 탐색을 종료합니다.
- 동생 위치에 도달한 경우 현재 최단 시간과 비교합니다.
- 더 짧은 시간이라면 최단 시간을 갱신합니다.
- 같은 최단 시간이라면 경우의 수를 증가시킵니다.
V1 구현 포인트
1. 현재 경로 방문 체크
현재 경로에서 이미 방문한 위치는 다시 방문하지 않도록 처리하였습니다.
if (visited[idx]) return;탐색이 끝난 뒤에는 다시 방문 가능하도록 복구하였습니다.
visited[idx] = 0;2. 최단 시간보다 오래 걸리는 경우 종료
이미 구한 최단 시간보다 오래 걸리는 경우는 더 이상 탐색하지 않았습니다.
if (level > ret) return;불필요한 탐색을 줄이기 위해 사용하였습니다.
3. 최단 시간과 경우의 수 관리
동생 위치에 도달했을 때 최단 시간을 갱신하였습니다.
if (idx == brother && level < ret) {
ret = level;
ret_cnt = 1;
return;
}같은 최단 시간으로 도달한 경우에는 경우의 수를 증가시켰습니다.
if (level == ret && idx == brother) {
ret_cnt++;
return;
}V2 코드
#include <bits/stdc++.h>
using namespace std;
int brother, subin;
int visited[100001];
int cnt[100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> subin >> brother;
queue<int> q;
q.push(subin);
visited[subin] = 1;
cnt[subin] = 1;
int now;
while(!q.empty()) {
now = q.front();
q.pop();
for (int next : {now-1, now+1, now *2}) {
if (0 <= next && next <= 100000) {
if (visited[next] == 0) {
q.push(next);
visited[next] = visited[now] + 1;
cnt[next] = cnt[now];
}
else if (visited[next] == visited[now] + 1) {
cnt[next] += cnt[now];
}
}
}
}
cout << visited[brother]-1 << '\n'
<< cnt[brother] << '\n';
return 0;
}V2 풀이 흐름
- 시작 위치를 큐에 넣고 BFS를 시작합니다.
- 현재 위치에서 이동 가능한 세 위치를 확인합니다.
- 처음 방문한 위치라면 최단 시간을 저장합니다.
- 해당 위치까지의 경우의 수도 함께 저장합니다.
- 같은 최단 시간으로 다시 방문한 경우에는 경우의 수를 누적합니다.
- BFS가 종료되면 동생 위치의 최단 시간과 경우의 수를 출력합니다.
V2 구현 포인트
1. visited 배열에 최단 시간 저장
방문 여부만 저장하는 것이 아니라 해당 위치까지의 최단 시간을 저장하였습니다.
visited[next] = visited[now] + 1;이를 이용하여 최단 거리 여부를 판단할 수 있었습니다.
2. 경우의 수 저장
각 위치까지 최단 시간으로 도달하는 경우의 수를 저장하였습니다.
cnt[next] = cnt[now];처음 방문한 경우에는 현재 위치의 경우의 수를 그대로 가져왔습니다.
3. 같은 최단 거리로 도달한 경우 처리
이 문제의 핵심이었던 부분입니다.
else if (visited[next] == visited[now] + 1) {
cnt[next] += cnt[now];
}이미 방문한 위치라도 같은 최단 시간으로 도달한 경우에는 새로운 최단 경로가 추가된 것이므로 경우의 수를 누적하였습니다.
예를 들어 어떤 위치에 도달하는 최단 경로가 2개 존재한다면, 이후 해당 위치를 통해 만들어지는 최단 경로들도 모두 반영될 수 있도록 처리하였습니다.
4. BFS를 이용한 최단 거리 계산
BFS는 먼저 방문하는 경로가 최단 경로임을 보장합니다.
따라서 처음 방문한 경우에는 해당 시간이 최단 시간이 되며, 이후 같은 시간으로 방문한 경우만 추가로 처리해주면 최단 시간과 경우의 수를 동시에 구할 수 있었습니다.
