[코딩테스트] [BOJ16947] 서울 지하철 2호선

문제

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

---

풀이

1. 역은 노드, 역과 역을 연결하는 구간은 간선으로 표현한 그래프(이중벡터)를 생성

2. 차수(연결된 노드 수)를 표현한 벡터 생성

3. 사이클을 판별하기 위해 차수가 1인 노드 삭제 및 사이클에서 제외
   3-1. 차수가 1인 노드와 인접한 노드를 순회하며 차수를 1씩 줄여준다 (제거된 노드 반영)
   3-2. 차수를 줄인 뒤 1이 되었다면 사이클에 포함되지 않기 때문에 제외시켜준다

4. bfs로 사이클에 판별되는 노드로부터 시작해 인접한 노드와의 거리를 구한다
   4-1. bfs는 최단거리를 보장하기 때문임

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	// 역의 개수
	int stationCount = 0;
	cin >> stationCount;

	// 간선 정보 추가한 그래프 생성
	vector<vector<int>> adj(stationCount);
	vector<int> degree(stationCount, 0);
	for (int i = 0; i < stationCount; i++)
	{
		int left, right;
		cin >> left >> right;
		--left;
		--right;

		adj[left].push_back(right);
		adj[right].push_back(left);

		degree[left]++;
		degree[right]++;
	}

	// 리프 노드 제거
	queue<int> leaf;
	vector<bool> inCycle(stationCount, true);
	for (int i = 0; i < stationCount; i++)
	{
		if (degree[i] == 1)
		{
			inCycle[i] = false;
			leaf.push(i);
		}
	}

	while (!leaf.empty())
	{
		int current = leaf.front();
		leaf.pop();

		for (int next : adj[current])
		{
			if (--degree[next] == 1)
			{
				inCycle[next] = false;
				leaf.push(next);
			}
		}
	}

	// bfs로 사이클 노드까지 최단 거리 도출
	queue<int> bfs;
	vector<int> distance(stationCount, -1);
	for (int i = 0; i < stationCount; i++)
	{
		if (inCycle[i])
		{
			distance[i] = 0;
			bfs.push(i);
		}
	}

	while (!bfs.empty())
	{
		int current = bfs.front();
		bfs.pop();

		for (int next : adj[current])
		{
			if (distance[next] < 0)
			{
				distance[next] = distance[current] + 1;
				bfs.push(next);
			}
		}
	}

	for (int i : distance)
	{
		cout << i << " ";
	}

	return 0;
}