문제
문제 분석
간선의 가중치가 동일하고 이동에 대한 최단 거리를 구하는 문제이다. 그런데 이 문제는 특이하게 1차원이다.
즉, 1차원 BFS 문제의 대표 유형이다.
최단 거리가 어떠한 경우에도 될 수 없는 경우는 다음과 같다.
- 이미 방문했던 곳을 또 방문하는 경우 (동선 낭비)
- 맵 범위 밖을 벗어나는 경우
길이가 8이고 수빈이가 3번 위치에 있을 때, X-1, X+1, 2*X 위치로 각각 이동시킬 때 각 위치의 최단 경로를 아래에서 살펴보자.
3번 위치에서 X-1, X+1, 2*X 지점은 각각 2,4,6 지점이다. 그래서 저 3개의 지점은 1번의 이동만으로 저 지점에 도달할 수 있다.
이제 케이스를 나눠서 생각해봐야 한다.
- 2번 지점으로 이동한 경우
- 4번 지점으로 이동한 경우
- 6번 지점으로 이동한 경우
2번 지점으로 이동한 경우에는 각각 1,3,4 번 지점으로 이동할 수 있는데, 3번과 4번 지점은 이미 방문했으므로 제외하고 표시하면 다음과 같다.
4번 지점으로 이동한 경우에는 각각 3,5,8번으로 이동할 수 있고 각 지점의 최단 거리 수를 작성하면 아래 그림과 같다.
6번 지점으로 이동한 경우도 작성하면 아래 그림과 같다.
이때 BFS 구현에서는 큐에 push을 하는 연산을 하게 되는데 이 성질을 이용해 최단 거리를 구할 수 있다.
왜냐하면 이동 거리가 1인 지점을 모두 push하고 이동을 한 다음 pop이 되고 1의 이동과 연결된 2의 이동이 push 되며 2의 이동이 진행되면서 pop을 진행하고 3의 이동이 push가 되는 것을 반복하기 때문이다.
따라서 이동 횟수가 적은 것부터 이동 횟수가 많은 순서대로 탐색을 진행하기 때문에 이러한 성질을 이용해서 최단 거리를 구하는 것이다.
정답 코드
- 문제 입출력에서 처음 수빈이가 위치한 곳은 이동 횟수로 취급하지 않기 때문에 이 점을 유념해야 한다.
- Tip) BFS/DFS 탐색 시 다음 이동할 위치의 조건을 따지는 부분에서 맵의 범위가 벗어났는지를 먼저 검사해주는 것이 중요하다. (배열로 지정한 Board 범위를 벗어나는 인덱스에 접근하려고 하면 인덱스 범위 오류가 발생하기 때문)
// 1차원 BFS 문제 (간선의 가중치가 동일)
// 수빈이는 점 100,000일 때 2*X를 해서 최대 200,000인 지점까지 이동할 수 있다.
// 수빈이가 음수로 가는 경우는 어떠한 경우에서도 동생을 가장 빠른 시간안에 찾을 수 없다.
#include <iostream>
#include <queue>
#define MAX_N 200001 // 최대로 갈 수 있는 지점은 200,000
using namespace std;
int Board[MAX_N]; // 각 위치마다 수빈이가 지나갈 수 있는 최단 거리 수를 표시할 배열
void bfs(int start_x, int finish_x) { // start_x는 수빈이의 시작 위치, finish_x는 동생의 위치
queue<int> q;
// 초기 노드 방문 처리
Board[start_x] = 1;
q.push(start_x);
while (!q.empty()) {
int cur_x = q.front();
q.pop();
if (cur_x == finish_x) {
cout << Board[cur_x]-1;
return;
}
int move[3] = { cur_x - 1, cur_x + 1, cur_x * 2 };
for (int next_x : move) {
if (next_x < 0 || next_x > 200000) continue; // 맵 범위 밖을 벗어나는 경우
if (Board[next_x] != 0) continue; // 이미 방문한 경우 또 방문하는 경우에는 최단 거리가 될 수 없음
// 다음 노드 방문처리
q.push(next_x);
Board[next_x] = Board[cur_x] + 1;
}
}
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N, K;
cin >> N >> K;
bfs(N, K);
return 0;
}
교훈점
1차원 BFS 탐색 유형에 대해 구현하는 연습을 하였다.
BFS 탐색 시 맵의 범위(할당된 배열의 범위 안에) 해당하는지 먼저 체크해줘야 배열 인덱스 오류가 나지 않는다.
