[알고리즘] 백준 온라인 저지 BOJ 1697 숨바꼭질 풀이 및 코드

1697 숨바꼭질

문제 해석

---

수빈이가 동생을 찾아가는데 몇초만에 찾는지 알아내는 문제입니다. 수빈이와 동생은 점 0~100000사이에 있습니다. 근데 왜 수빈이만 동생을 찾는 건지는 이해가 가지 않는군요. 

수빈이는 다음과 같은 이상한 능력이 있습니다.

1. 수빈이가 위치 X에 있을때 1초에 X+1, X-1의 위치로 걸을 수 있습니다. 물론 범위 0~100000의 범위 안에서만 말이죠.

2. 수빈이는 순간이동을 할 수 있는데, 현재 위치 X에서 1초만에 X*2의 위치로 이동할 수 있습니다.

두개의 입력이 주어지는데, 가장 첫번째 입력은 수빈이의 위치, 두번째 입력은 동생의 위치입니다.

5와 17이라는 입력이 주어진다면 답은 4가 됩니다. 5->10->9->18->17로 찾을 수 있습니다.

이런 조건 속에서 몇 초만에 동생을 찾을 수 있을까요?

풀이

---

BFS(Breadth First Search)를 이용하면 이 문제를 풀 수 있습니다. 그 때문에 큐(Queue)를 이용해야합니다. 수빈이가 있는 점을 start라고 하고 동생이 있는 위치를 end라고 합시다. 결국 우리가 구현해야하는 것은 start에서부터 BFS를 통해 end까지 도달을 몇번에 할 수 있는가입니다.

아래의 전체적인 코드를 우선 보고 설명하도록 하겠습니다.

#include <cstdio>
#include <queue>

using namespace std;
#define MAX_N 100001
#define LIMIT 100000
int bfs(int start, int end) {
	if (start==end) return 0;
	queue<int> q;
	q.push(start);
	int length[MAX_N] = { 0, };

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		if (here + 1 <= LIMIT) {
			if (here + 1 == end)
				return length[here] + 1;
			if (!length[here + 1]) {
				length[here + 1] = length[here] + 1;
				q.push(here + 1);
			}
		}
		if (here - 1 >= 0) {
			if (here - 1 == end) return length[here] + 1;
			if (!length[here - 1]) {
				length[here - 1] = length[here] + 1;
				q.push(here - 1);
			}
		}
		if (here * 2 <= LIMIT) {
			if (here * 2 == end) return length[here] + 1;
			if (!length[here * 2]) {
				length[here * 2] = length[here] + 1;
				q.push(here * 2);
			}
		}

	}
	return -1;
}
int main() {
	int start, end;
	scanf("%d %d", &start, &end);
	printf("%d\n", bfs(start, end));
	return 0;
}

코드에서 가장 눈여겨 봐야할 곳이 bfs함수입니다. bfs는 두개의 인자를 전달받는데 우리가 아까 이야기했던 start와 end이지요.

bfs내부에서는 start와 end가 같은 위치일 수 있으므로 가장 먼저 start와 end가 같은지 확인하며 참이라면 bfs를 순회할 필요없이 바로 0을 반환해줍니다.

이제 본격적인 bfs 탐색을 시작합니다. q에는 다음 순회할 노드들이 들어가며, length배열에는 그 점까지 몇번에 걸쳐 오는가를 저장하게 됩니다. 예를 들어 5->10->11->12까지 순회했다고 친다면 length[5]=0, length[10]=1, length[11]=2, length[12]=3이라는 값을 갖게 되는 겁니다. 이 변수에 0이 아닌 양수의 값이 있다는 것은 이미 그 점을 방문한 것이 되므로 q에 이 점을 push하지 않습니다.

처음 start의 점을 큐에 push한 이후에 q가 빌때까지 while루프를 돕니다. while루프 안에는 here라는 변수로 큐의 점을 꺼내옵니다. 처음에는 start가 들어있으니, start의 점을 꺼내오겠죠?

그 점이 here가 되고, here에서 +1, -1, *2가 범위에 속해있으며, 그 점이 바로 end와 같은 점이라면 현재 length[here]에서 1을 추가한 값을 반환합니다.

end와 같은 점이 아닐 경우에는 length에 다음 q에 추가될 점(here+1, here-1, here*2)이 기록이 되었나(length[here+1], length[here-1], length[length*2]에 0이 아닌 양수의 값이 있으면 이미 그 점을 전에 방문했다는 겁니다.)를 확인하고 length에 기록이 되어있지 않다면 length를 기록하고 q에 push합니다.

bfs함수에서 while루프의 if조건문에 의한 반환이 반드시 이루어집니다. +1,-1을 통해서 0~100000까지 전부 방문 가능하니까요.

결론은 bfs를 이용하면 그리 어렵지 않게 풀수 있는 문제였습니다.