# 문제 설명
1697 숨바꼭질 문제 링크 : https://www.acmicpc.net/problem/1697
수빈이는 점 N, 동생은 점 K에 있다.
이 때, N과 K의 범위는 0 이상 100,000 이하이다.
수빈이는 걷거나 순간이동을 할 수 있다. 만일 수빈이의 위치를 X라고 하면,
1초 후 X-1 / X+1 / X*2 로 이동할 수 있다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지를 구하라.
# 문제 풀이
'가장 빠른 시간'이므로 BFS로 접근하기 시작했다.
먼저 수빈이와 동생의 위치인 N,K를 각각 입력받고, 각 지점의 위치와 그 위치를 방문했을 때 가장 짧게 걸린 시간을 저장할 Q를 선언한다.
이 때 int visit[100001] 배열은 각 위치가 방문되었을 때 가장 짧게 걸린 시간을 저장하는 배열이다.
즉, 이 문제에서 구하는 답은 visit[K]로 정의할 수 있게 된다.
climits 라이브러리를 사용해서 visit[] 값을 INT_MAX로 초기화한다 (최솟값을 구하는 것이기 때문에 가능한 한 최댓값으로 설정해야 안전함)
만일 N과 K가 같을 때를 대비하여 예외처리로 같은 경우 0초를 출력하고 함수를 종료하는 것으로 예외를 처리했다.
같지 않다면, BFS를 돌게 되는데 초기값은 N으로, visit[N] == 0으로 시작하게 된다.
현재 방문중인 점(top.first)의 위치가 K이면 visit[K]를 top.second와 비교해서 가장 최솟값으로 업데이트한다.
또, visit[K]보다 현재 방문중인 점의 시간(top.second)이 크면 지금 방문중인 점을 기준으로 더 진행해봐도 visit[K]보다 더 짧은 시간 내에 K에 도달할 수 없으므로 더 이상 진행하지 않는다 (continue 처리)
top.first + 1, top.first - 1, top.first * 2를 계산해서 범위 안에 들어오는지(0 이상 100,000 이하인지)를 체크하고 지금 방문하려고 하는 다음 점이 지금 경로로 방문했을 때 최단 시간이 맞는지(visit[다음 위치]보다 top.second + 1이 더 작아야지만 방문하는 의미가 있음) 체크하고 최단 시간이 맞다면 큐에 넣고 K에 방문할 때까지 계속해서 진행한다.
BFS가 끝나고 나면 visit[K]를 출력한다. (K 위치에 방문하는 가장 최단 시간이 저장되어 있음)
// 1697. 숨바꼭질
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <climits>
#include <queue>
#include <cstring>
using namespace std;
int N, K;
int visit[100001];
int main() {
cin >> N >> K;
queue<pair<int, int> > Q;
for (int i = 0; i <= 100000; i++) {
visit[i] = INT_MAX;
}
Q.push({ N, 0 });
visit[N] = 0;
if (N == K) {
cout << 0 << endl;
return 0;
}
while (!Q.empty()) {
pair<int, int> top = Q.front();
Q.pop();
if (top.first == K) {
visit[K] > top.second ? visit[K] = top.second : NULL;
continue;
}
if (visit[K] < top.second) continue;
if (top.first + 1 <= 100000 && visit[top.first + 1] > top.second + 1) {
Q.push({ top.first + 1, top.second + 1 });
if(visit[top.first + 1] > top.second + 1) visit[top.first + 1] = top.second + 1;
}
if (top.first - 1 >= 0 && visit[top.first - 1] > top.second + 1) {
Q.push({ top.first - 1, top.second + 1 });
if (visit[top.first - 1] > top.second + 1) visit[top.first - 1] = top.second + 1;
}
if (top.first * 2 <= 100000 && visit[top.first * 2] > top.second + 1) {
Q.push({ top.first * 2, top.second + 1 });
if (visit[top.first * 2] > top.second + 1) visit[top.first * 2] = top.second + 1;
}
}
cout << visit[K] << endl;
}# 개선점 및 보완할 점
일차적으로, 문제를 대충 읽는 습관이 아직 보완되지 않았다.
백준 채점 기준으로 52%에서 계속 '틀렸습니다'가 나왔는데, 그 이유가 N과 K의 범위를 충분히 고려하지 않아서 visit 배열의 크기 및 초기화를 잘못 설정했기 때문이었다.
또, BFS를 할 때에 시간 초과를 고려한 가지치기 조건을 거는 데에 아직 미숙한 것 같다.
처음에 K에 도달할 수 없을 것 같은 값(예를 들어 K 값이 17인데 5000까지 방문할 필요는 없는데 계속 방문함)이 계속 나오고 무한 루프에서 빠져 나오질 못해서 BFS에서 조건을 걸 때 top.first + 1 < 2 K 이런 식으로 조건을 걸었더니 '틀렸습니다'가 계속 나왔다.
경로를 설정할 때 2K까지 방문을 해봐야만 최단 시간 내에 K에 도달하는 경로도 있을 지도 모르기 때문에 꽤나 경솔한 조건이었다.
'최단 시간'에 포인트를 잡고 방문을 가장 효율적으로 하려면 위치가 아니라 시간을, 지금 방문하는 루트가 효율적이려면 각 점마다의 시간을 제한해야 겠다 생각하니 문제가 풀렸다.
1년전에 같은 문제를 풀었을 때보다 메모리와 시간이 줄어들어서, 풀었던 문제도 다시 돌아봐야겠다는 중요성을 느꼈다.
