[백준 16947] 서울 지하철 2호선 (C++)

문제 링크: www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

1. 주의할 점

- DFS + 메모아이징을 통해 구현하거나 글쓴이처럼 빙글빙글 돌아가게 풀지 않으면 TLE가 날 문제일것 같다 (N<=3000 때문)

- '정점 개수 = 간선 개수'의 조건에서는 순환선이 무조건 1개만 존재한다

- 환승지점(연결된 역이 3개 이상)은 연결된 역이 3,4,5,.... 쭉 있을 수 있다 (Ex. Star 형태)

 

2. 구현

- 환승지점을 미리 구해놓는다 -> Transfer 큐에 저장

- find_dup() 함수를 통해 1번 역에서 시작해서 BFS 과정을 거쳐서 방문이 겹치는 지점을 구해서 Start에 저장한다 -> Start는 무조건 순환선에 속하기 때문에 구했다

- find_cycle() 함수를 통해 Start에서 시작하여 BFS 과정을 거쳐서 방문이 겹치는 지점과 그 직전 지점을 Ans 큐에 넣는다(단, 이 과정에서는 Before[] 배열을 통해 경로를 저장해놓는다)

- Ans 큐와 Before[] 배열을 통해 순환선을 구하고, Dist[] 배열값을 전부 0으로 설정한다

- Transfer큐에 속하면서, DIst[] 값이 0인 역을 Result 큐에 넣는다 -> 지선을 구하기 위해. 단, 이때 DIst[] 값이 0인 역만 넣는 이유는, 문제의 예제 5번에서 3번역과 같이 환승역이지만, 순환선이 아닌 역을 거르기 위함이다.

- Result 배열에서 1개씩 뽑으면서 해당 역에 지선이 있다면 순환선까지의 거리를 저장하고 Result에 넣는 방식으로 모든 역의 Dist[]값을 구한다

 

#define MAX 987654321
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int pre, now;
};
info tmp;
vector<int> v[3001];
int num, s, e, start = -1;
int check[3001];
int before[3001];
int dist[3001];

void cal(int pre, int cur) {
	check[cur] = check[pre] + 1;
	for (int i = 0; i < v[cur].size(); i++) {
		if (check[v[cur][i]] == 0)
			cal(cur, v[cur][i]);
	}	
}

void find_cycle() {
	for (int i = 1; i <= num; i++) {
		check[i] = 0;
		dist[i] = -1;
	}
	check[start] = 1;
	queue<info> q;
	queue<int> ans;
	tmp.pre = start;
	before[start] = start;
	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		check[next] = 1;
		tmp.now = next;
		q.push(tmp);
		before[next] = start;
	}
	bool finish = false;
	while (!q.empty()) {
		int cp = q.front().pre;
		int cn = q.front().now;
		q.pop();
		for (int i = 0; i < v[cn].size(); i++) {
			int next = v[cn][i];
			if (next != cp) {
				if (check[next] != 0) {		//반대에서 만나는 지점
					ans.push(next);
					ans.push(cn);
					finish = true;
					break;
				}
				else {
					check[next] = 1;
					tmp.pre = cn;
					tmp.now = next;
					q.push(tmp);
					before[next] = cn;
				}
			}
		}
		if (finish) break;
	}

	while (!ans.empty()) {
		int cidx = ans.front();
		ans.pop();
		dist[cidx] = 0;
		if (cidx == start) continue;
		else
			ans.push(before[cidx]);
	}
}

//내부 순환선에 속하는 역을 1개 찾는다
void find_dup() {
	queue<info> q;
	tmp.pre = 1;
	check[1] = 1;
	for (int i = 0; i < v[1].size(); i++) {
		tmp.now = v[1][i];
		q.push(tmp);
		check[v[1][i]] = 1;
	}
	while (!q.empty()) {
		int cp = q.front().pre;
		int cn = q.front().now;
		q.pop();
		for (int i = 0; i < v[cn].size(); i++) {
			int next = v[cn][i];
			if (next != cp) {
				if (check[next] == 1) {
					start = next;
					break;
				}
				else {
					check[next] = true;
					tmp.now = next;
					tmp.pre = cn;
					q.push(tmp);
				}
			}
		}
		if (start > 0) break;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}
	queue<int> transfer, result;
	//환승지점을 구해놓는다
	for(int i=1;i<=num;i++)
		if (v[i].size() > 2) {
			transfer.push(i);
		}
	find_dup();
	find_cycle();

	//순환선이면서 환승인 지점 Result에 넣기
	while (!transfer.empty()) {
		int cidx = transfer.front();
		transfer.pop();
		if (dist[cidx] == 0)
			result.push(cidx);
	}
	//거리 구하기
	while (!result.empty()) {
		int cidx = result.front();
		result.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (dist[next] == -1) {
				dist[next] = dist[cidx] + 1;
				result.push(next);
			}
		}
	}
	for (int i = 1; i <= num; i++)
		cout << dist[i] << " ";
	return 0;
}