미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!
https://www.acmicpc.net/problem/12851
숨바꼭질 2
풀이
이전에 풀었던 문제인 숨바꼭질 3의 전편(?) 같은 느낌이다.
숨바꼭질 3에서의 순간이동이 0초였다면, 이곳에서는 1초라고 한다.
이번에는 BFS를 활용한다.
각 좌표가 노드라고 생각하고, 다음 노드는 각각
X + 1, X - 1, X * 2가 된다.
방문 표시를 할 때 유의할 사항이 있다. 원래의 BFS를 생각하면, 큐에 노드를 넣을 때 마다 방문 체크를 해주었다.
그런데, 여기서는 그렇게 진행하면 안 된다. 그 지점까지 가는 다른 방법들이 존재하고, 그 방법들의 수를 구하는 것이 이 문제의 목표이기 때문이다.
그러면 방문 체크를 어디서 해야할까?
그것은 바로 pop을 한 이후이다. pop을 한 이후에는 그 지점까지 최단 거리로 이동하는 방법은 존재하지 않는다는 점을 이용하는 것이다.
예를 들어, 수빈이는 현재 1의 지점에 있고 동생이 2의 지점에 있다고 하자.
그렇다면 방법은 아래의 2가지가 있다.
1. 1에서 오른쪽으로 한 칸 걷기.
2. 1에서 순간이동하기.
이를 BFS에서 일반적으로 처리하는 경우를 보자.
if (!visited[x + 1]) {
visited[x + 1] = true;
queue.push(x + 1);
}
if (!visited[x * 2] {
visited[x * 2] = true;
queue.push(x * 2);
}
이 경우에는 결과는 1개만 나온다. 왜?
이미 이동하려는 곳은 방문 처리가 되어서 순간이동의 경우를 고려할 수 없기 때문이다.
1에서 오른쪽으로 한 칸 걷기 -> 방문 처리
1에서 순간이동하기 -> 이미 방문 처리되어 있어서 방문하지 않음
그래서, 방문 처리를 큐의 값을 pop한 이후에 하게 되면 위 문제를 해결할 수 있다.
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;
bool visited[100001];
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int N, K;
cin >> N >> K;
queue<pair<int, int>> q;
q.push({ N, 0 });
int answer = 0;
int min_count = 987654321;
while (!q.empty()) {
pair<int, int> xc = q.front();
q.pop();
int x = xc.first;
int c = xc.second;
// 지금 위치까지 오는 다른 최단 경로의 존재 가능성이 있음.
// 그래서 큐에 푸쉬할 때 방문 설정을 하는 것이 아닌,
// 큐에서 팝되는 순간에 방문 설정을 함.
visited[x] = true;
if (x == K) {
if (c < min_count) {
answer = 1;
min_count = c;
}
else if (c == min_count) {
answer++;
}
}
else {
if (x + 1 <= 100000 && !visited[x + 1])
q.push({ x + 1, c + 1 });
if (x - 1 >= 0 && !visited[x - 1])
q.push({ x - 1, c + 1 });
if (x * 2 <= 100000 && !visited[x * 2])
q.push({ x * 2, c + 1 });
}
}
cout << min_count << endl;
cout << answer << endl;
return 0;
}
'코딩 테스트(Coding test) > BOJ' 카테고리의 다른 글
[BOJ 11725/C++] 트리의 부모 찾기 (0) | 2022.12.07 |
---|---|
[BOJ 1967번/C++] 트리의 지름 (0) | 2022.11.23 |
[BOJ 16953번/C++] A → B (0) | 2022.11.15 |
[BOJ 1991번/C++] 트리 순회 (0) | 2022.11.13 |
[BOJ 1918번/C++] 후위 표기식 (0) | 2022.11.11 |