[백준 1697/C++] 숨바꼭질

1. 문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int dist[200005];
int nx[3] = { -1,1,2 };

int main(void) {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	int N, K;
	cin >> N >> K;
	queue<int> Q;
	for (int i = 0; i < 200005; i++) 
		dist[i] = -1;
	if (N == K) {
		cout << 0; return 0;
	}
	Q.push(N); dist[N] = 0;
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		int dx = 0;
		for (int i = 0; i < 3; i++) {
			if (i == 2)
				dx = cur * nx[i];
			else
				dx = cur + nx[i];
			if (dist[dx] > 0 || dx < 0 || dx > 100000) continue;
			if (dx == K) {
				cout << dist[cur] + 1;
				return 0;
			}
			dist[dx] = dist[cur] + 1;
			Q.push(dx);
		}
	}
}

---

2. 문제 평가 및 해설

드디어 BFS 마지막 유형이다. 마지막 유형은 기존의 BFS와 다르게 1차원 map을 가진다. 

1차원 map이기 때문에, 굳이 map 배열을 만들어 줄 필요가 없다. 배열을 만들라면 만들 수 있겠지만, index가 음수이거나 매우 커질 때, 발생하는 문제를 예외처리를 해줘야할 것 같다.

기존의 BFS 문제와 풀이 방법은 같다.

1. 순간이동, 왼쪽, 오른쪽으로 이동하는 배열을 만들어준다.

2. for문을 돌면서, 왼쪽/오른쪽/순간이동 case를 넣어준다.

3. 방문한 노드이면 예외처리를 해준다. 여기서 음수이거나 100000을 넘으면 예외처리를 해주었는데, 이 부분은 사실 굳이 안해줘도 되긴 한다. 왜냐하면 수빈이와 동생의 위치만 0~100000으로 지정해주었지, 이동하는 범위는 제한을 걸어주지 않았기 때문이다. 그래서 수빈이는 최대 200000까지 이동할 수 있다. 예외처리를 굳이 안해도 되긴 하지만, 곰곰히 생각해보면 음수이거나 200000으로 넘어서는 경우는 최단 시간이 될 수 없다. 100000를 초과해서 왼쪽으로 계속 이동하는 경우이거나 0을 초과(?)해서 오른쪽으로 계속 이동하는 경우는 최단 시간이 될 수 없다.

본문의 코드가 약간 지저분하긴 한데, 바킹독 님의 풀이를 보고 조금 다듬어보았다. for ranged loop의 사용법을 하나 더 알게되었다. 다듬은 풀이는 다음과 같다. 

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int dist[100001];

int main(void) {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	int N, K;
	cin >> N >> K;
	fill(dist, dist + 100001, -1);
	queue<int> Q;
	Q.push(N); dist[N] = 0;
	while (dist[K] == -1) {
		int cur = Q.front(); Q.pop();
		for (int nxt : {cur-1,cur+1,2*cur}) {
			if (nxt < 0 || nxt > 100000) continue;
			if (dist[nxt] != -1) continue;
			dist[nxt] = dist[cur] + 1;
			Q.push(nxt);
		}
	}
	cout << dist[K];
}