[baekjoon 2021] 최소 환승 경로 (BFS, 0-1 BFS, 다익스트라) (C++)

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

2021번: 최소 환승 경로

지하철 노선과 그 노선을 지나는 역의 개수가 주어진다.

이 정보를 갖고 어떻게 그래프화 시켜서 이동을 할까 고민을 했는데, 해당 역을 지나는 노선 정보와 노선을 지나는 역, 이 두 개를 저장했다.

<input>

10 3

1 2 3 4 5 -1 // 1번 노선

9 7 10 -1 // 2번 노선

7 6 3 8 -1 // 3번 노선

1 10

의 경우 route벡터에는 노선 번호에 해당하는 역들이 저장된다.

route[1] = 1, 2, 3, 4, 5

route[2] = 9, 7, 10

route[3] = 7, 6, 3, 8 이 저장된다.

 

station벡터에는 그 역을 지나는 노선의 번호가 저장된다.

station[1] = 1

station[2] = 1

station[3] = 1, 3

station[4] = 1

station[5] = 1

station[6] = 3

station[7] = 2, 3

station[8] = 3

station[9] = 2

station[10] = 2 가 저장된다.

 

이후 원래 기존 BFS 할 때에는 해당 점과 연결된 다른 점을 바로 방문했다면

이 문제의 경우 시작 역을 통해 station [시작 역]을 지나는 노선의 번호를 찾고, 이후 route [시작 역과 연결된 노선의 번호]를 통해 연결된 노선에 해당하는 역을 방문하는 식이다.

 

좀 헷갈리는데, 역 -> 역에 연결된 노선 -> 찾은 노선에 해당하는 다음 역들 순으로 방문한다.

이 경우가 환승 횟수 1이 추가된다.

 

따라서, 방문 시 현재 값 + 1을 저장해준다.

 

check 배열은 거리 및 방문 정보 저장, routeCheck는 한 번 방문한 노선은 해당 역들을 이미 한번 훑은 상태이므로 방문하지 않기 위해 정보를 저장해준다.

 

BFS를 시작하기 전에 시작점을 -1로 해주는데, 시작점과 연결된 점들도 check [연결점] = check [시작점]+1의 공식이 적용되므로 환승 횟수를 0으로 만들기 위함이다. (시작점과 같은 노선에 있는 경우 환승 횟수가 0이므로)

이후 시작점과 연결된 노선을 싹 훑고, 큐에 한 번씩 들어가고, 그 점들에 연결된 노선을 또 훑고이 반복된다.

마지막으로 시작점의 횟수를 0으로 바꿔주면서 함수를 종료한다.

 

10 3

1 2 3 4 5 -1 // 1번 노선

9 7 10 -1 // 2번 노선

7 6 3 8 -1 // 3번 노선

1 10

큐에 들어가는 순서 (노드, 환승 횟수)로 표기한다.

(1, -1) -> 역 1번은 노선 1번이므로 노선 1번에 해당하는 역들 방문

(2, 0) (3, 0) (4, 0), (5, 0) -> 역 2, 4, 5번은 노선 1번에만 해당하고, 노선 1번은 방문했으므로 종료, 역 3번만 노선 3번으로 간다

(7, 1) (6, 1) (3번은 방문했으므로 x) (8, 1) -> 역 7번을 통해 노선 2번으로 간다

(9, 2) (7번은 방문했으므로 x) (10, 2) -> 목표인 10번 역을 찾았으므로 종료

첫 번째 역 (1, 0)으로 바꿔주면서 끝

이런 식으로 큐에 들어가고, 방문을 하게 된다.

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int N, L, num, start, target;
vector<int> route[100001];
vector<int> station[100001];
int check[100001];
bool routeCheck[100001];

void BFS(int startX) {
	queue<int> q;
	q.push(startX);
	check[startX] = -1;

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (auto nextRoute : station[x]) {
			if (routeCheck[nextRoute])
				continue;
			routeCheck[nextRoute] = true;
			for (auto nextStation : route[nextRoute]) {
				if (check[nextStation] == INF) {
					check[nextStation] = check[x] + 1;
					q.push(nextStation);
				}
			}
		}
	}
	check[start] = 0; // 0으로 초기화, start와 end가 같은 경우 환승 횟수는 0이다
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> L;

	for (int i = 1; i <= L; i++) {
		while (1) {
			cin >> num;
			if (num == -1)
				break;
			route[i].push_back(num); // 루트를 지나는 역
			station[num].push_back(i); // 역에 연결된 루트 저장
		}
	}
	cin >> start >> target;

	for (int i = 1; i <= N; i++) {
		check[i] = INF;
	}

	BFS(start);

	if (check[target] == INF)
		cout << -1;
	else
		cout << check[target];
}

처음에 check 배열을 INF로 초기화하지 않고, -1로 초기화 후 BFS에서 거리 값을 리턴하도록 제출했는데 채점 100퍼센트에서 계속 틀렸다고 나왔다.

그 이유는 아직 잘 모르겠다..

 

+ 추가적으로 0-1 BFS나 다익스트라로 푼 풀이도 있다. 일단 풀어보고 다른 분들의 풀이를 보면서 공부를 해보자.

같은 노선에 해당하는 역은 0의 가중치, 다른 노선에 있는 역은 1의 가중치이므로 0-1 BFS 풀이가 가능한 것 같다.

 

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

5214번: 환승

아주 비슷한 문제로 환승 문제가 있다. 이 문제는 역 이동 또한 가중치가 1로 들어가므로 입력값만 잘 자료구조에 저장하면 쉽게 풀릴 것이다.