마지막으로 1차원 배열에서의 BFS를 살펴보자.
지금까지는 2차원 배열에서 상하좌우로 탐색하는 방식으로 BFS를 진행해 왔다. 하지만 BFS는 1차원 배열에서도 사용될 수 있다. 상하좌우로 움직이는 것이 아닌, 특정 칸 수를 뛰어 넘어서 움직인다와 다양한 조건에서도 BFS를 활용할 수 있다.
사용 예시
BOJ 1697 숨바꼭질
문제 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int dist[100001];
int N, K;
queue<int> Q;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
Q.push(N);
fill(dist, dist + 100001, -1);
dist[N] = 0;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
// 1. X - 1
int nxt = cur - 1;
if (nxt <= 100000 && nxt >= 0) {
if (dist[nxt] < 0) { // 방문한 적 없을때
dist[nxt] = dist[cur] + 1;
Q.push(nxt);
}
if (nxt == K) {
cout << dist[K];
return 0;
}
}
// 2. X + 1
nxt = cur + 1;
if (nxt <= 100000 && nxt >= 0) {
if (dist[nxt] < 0) { // 방문한 적 없을때
dist[nxt] = dist[cur] + 1;
Q.push(nxt);
}
if (nxt == K) {
cout << dist[K];
return 0;
}
}
// 3. 2 * X
nxt = cur * 2;
if (nxt <= 100000 && nxt >= 0) {
if (dist[nxt] < 0) { // 방문한 적 없을때
dist[nxt] = dist[cur] + 1;
Q.push(nxt);
}
if (nxt == K) {
cout << dist[K];
return 0;
}
}
}
}수빈이의 출발 위치를 큐에 넣고, (수빈이의 위치 - 1), (수빈이의 위치 + 1), (수빈이의 위치 * 2)의 3가지 경우를 고려해서 BFS를 진행하여 만약 동생의 위치에 값을 갱신하게 된다면 동생을 찾은 것이므로 그 값을 반환하고 프로그램을 종료한다.
여기서 주의할 점은 배열을 100001의 크기로 선언했는데, 문제 조건에서는 처음 위치만 0 ~ 100000사이라고 했지 이동할 때의 위치는 제한이 없으므로 1000001을 넘어갈 수 있다. 최단 시간을 찾는 것이기 때문에 100000을 넘어가는 경우는 없지만 다른 문제에서 주의할 필요는 있어 보인다.
또한 foreach문을 사용해서 for(int nxt : {cur - 1, cur + 1, cur * 2}) 와 같이 구현했으면 좀 더 효율적이었을 것 같다.
