[APS][C++] BOJ G3 16947번 서울 지하철 2호선

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

---

문제

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

• 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다.
• 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다.
  • 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다.
  • 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

• 총 N개의 정수를 출력한다.
  • 1번 역부터 N번 역까지 순환선 사이의 거리를 공백으로 구분해 출력한다.

---

풀이

1. 순환선에 속하는 역을 찾는다. ➡️ 해당 번호의 역이 순환선에 속하는 역이라면 순환선까지의 거리는 항상 0이다.
   • 그래프에서 순환을 찾는 방법은 다양하다. 이번 풀이에서는 차수 1제거 반복(Leaf Pruning, 잎 제거 기법)을 사용하여 사이클에 속하는 정점을 찾았다.
2. 너비우선탐색(BFS)을 이용해서 순환선까지의 최단 경로를 찾는다.
   • 순환선에 속하는 모든 역들을 Queue에 넣고 BFS를 시작한다. ➡️ 이미 순환선을 찾은 후 거리가 모두 0이기 때문에 순환선끼리만 연결되어 있는 정점들은 자연스럽게 무시된다.

---

코드

#include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

int n;

vector<bool> cycle; // 순환역 확인
vector<int> dist; // 순환역까지 거리
vector<vector<int>> station; // 역 그래프

int main() {
	cin >> n;

	cycle.resize(n + 1, true);
	dist.resize(n + 1, INT_MAX);

	station.resize(n + 1);

	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;

		station[from].push_back(to);
		station[to].push_back(from);
	}

	// 순환 정점 확인
	// 잎(1차수) 제거 기법으로 순환 정점 확인
	vector<int> deg(n + 1, 0);
	for (int i = 1; i <= n; i++) deg[i] = (int)station[i].size();

	queue<int> que;
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1) que.push(i);
	}

	while (!que.empty()) {
		int now = que.front();
		que.pop();

		cycle[now] = false;

		for (size_t i = 0; i < station[now].size(); i++) {
			int next = station[now][i];
			if (!cycle[next]) continue;

			deg[next]--;

			if (deg[next] == 1) que.push(next);
		}
	}

	// 순환역으로부터 최단 거리 구하기
	// BFS 시작점
	queue<int> bque;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			dist[i] = 0;
			bque.push(i); // Queue에 순환역 넣고 시작
		}
	}

	while (!bque.empty()) {
		int now = bque.front();
		bque.pop();

		for (size_t i = 0; i < station[now].size(); i++) {
			int next = station[now][i];

			if (dist[next] != INT_MAX) continue;

			dist[next] = dist[now] + 1;
			bque.push(next);
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " ";
	}

	return 0;
}

---

결과