백준 16947 서울 지하철 2호선 c++ (dfs/bfs)

문제 출처 : https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

문제

서울 지하철 2호선은 다음과 같이 생겼다.

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

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

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

입력

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

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

처음 풀어보는 양방향 그래프에서의 사이클 찾기 문제이다.

문제에서 순환선이란 사이클을 말하며, 순환선을 포함한 모든 역에서 순환선 사이의 거리를 구해야 한다.

사이클을 찾은 이후, 사이클에 있는 역들은 모두 순환선에 포함되기 때문에, 순환선과의 거리는 모두 0이고,

지선(사이클이 아닌 노드)과 순환선 사이의 거리만 구하면 된다.

 

따라서 전체적인 풀이는, 사이클을 찾아 저장해놓고, 사이클에 속한 노드들을 큐에 모두 푸시하여 bfs로 사이클에 해당하는 노드에서 지선의 거리를 구하면 된다.

 

양방향 사이클에서 사이클을 찾는 방법은, 간선이 백엣지(BackEdge)일 때를 찾아야 한다.

1 3

3 2

2 4

4 5

5 2

의 간선이 주어졌을 때,

1 -> 3 ->2 -> 4-> 5 -> 2

위와 같이 다시 조상 노드로 돌아가는 마지막 간선 5->2를 백엣지라고 하며, 2,4,5,2가 사이클을 이룬다.

 

양방향 그래프이기 때문에

1 2

2 3

의 간선이 주어졌을 때는

1 -> 2 -> 3 -> 2 혹은 1-> 2 -> 1 같은 경로가 나올 수 있는데,

3의 다음 노드가 다시 조상 노드로 돌아가긴 했지만, 2는 3의 부모 노드이기 때문에 사이클이 아닌 그냥 간선을 거꾸로 탄 것일 뿐이다.

 

즉, 양방향 그래프의 사이클을 구하는 로직은, 이전에 현재 노드의 부모 노드가 아니면서, 이전에 방문했던 노드라면 사이클이 이루어진다!

 

주어진 문제에선 하나의 사이클만 존재하므로, 사이클을 찾게 되면, 이전에 지나왔던 노드들을 역추적하여 사이클의 노드들을 저장하고, 사이클 탐색을 종료했다.

 

이후, 저장한 사이클의 노드들을 모두 q에 푸시하여 bfs 탐색을 하고, 다음 노드가 사이클인 노드일 만나면 종료하고, 사이클이 아닌 노드를 만나면 거리를 1 추가하고 탐색을 이어간다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 3001
using namespace std;
//3<=n<=3000
//모든 정점의 순환선에 대한 거리를 출력
int n;
bool cycle[MAX];//사이클 노드 저장
vector<int> edge[MAX];//간선
bool visited[MAX];
int pre[MAX];//이전 방문했던 노드들(사이클 찾을 때 사용)
bool hasCycle;
int dist[MAX];
void bfs() {
	
	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			visited[i] = true;
			q.push({ i,0 });
		}
	}
	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();
		visited[cur] = true;
		
		for (int i = 0; i < edge[cur].size(); i++) {
			int next = edge[cur][i];
			if (visited[next]) continue;
			dist[next] = dis + 1;
			q.push({ next,dis + 1 });
		}
	}
}

void findCycle(int cur) {
	visited[cur] = true;
	for (int i = 0; i < edge[cur].size(); i++) {
		//사이클을 찾았다면 다른 dfs 모두 종료
		if (hasCycle) return;
		int next = edge[cur][i];
		if (visited[next]) {
			//부모가 아닌 다른 방문했던 노드(역간선)이면 사이클임
			if (next != pre[cur]) {
				//사이클 완성, cycle에 사이클 노드 저장
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
			
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;
		edge[from].push_back(to);
		edge[to].push_back(from);
	}
	findCycle(1);
	memset(visited, false, MAX);
	bfs();
	for (int i = 1; i <= n; i++) {
		cout << dist[i]<<' ';
	}
	return 0;
}