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를 이용하면 그리 어렵지 않게 풀수 있는 문제였습니다.
반응형
'알고리즘 > BFS' 카테고리의 다른 글
| [알고리즘] 백준 온라인 저지 BOJ 2178 미로탐색 (0) | 2018.09.24 |
|---|---|
| [알고리즘 : 그래프 이론] 그림으로 보는 BFS 기본, 개념, 설명 (0) | 2018.09.16 |
REAKWON
와나진짜
