[백준/BOJ] 백준 16947번 : 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

 

역들의 관계로 그래프를 만들고, 직전에 방문했던 위치는 방문하지 않는 dfs를 수행하여, SCC(강한 연결 요소)를 만드는 것과 비슷한 방법으로, 사이클에 속한 정점들을 판별했다. 그리고, 각 정점(역)에서 사이클(순환선)까지 최단 거리는 해당 정점에서 사이클까지 bfs(너비 우선 탐색)를 수행하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int n;
vector<int> adj[3005];
int visited[3005];
int visited_cnt = 0;
int cycle_check[3005];
stack<int> st;
vector<int> result;

//SCC와 비슷한 접근으로 사이클 판별
int dfs(int here, int before) {

	visited_cnt++;
	visited[here] = visited_cnt;

	st.push(here);
	int parent = visited[here];

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (there == before) {
			continue;
		}

		if (visited[there] == 0) {
			parent = min(parent, dfs(there, here));
		}

		//사이클이 존재할 때
		else {
			parent = min(parent, visited[there]);
		}
	}

	if (visited[here] == parent) {
		vector<int> cycle_node;

		while (!st.empty()) {
			int node = st.top();
			st.pop();

			cycle_node.push_back(node);

			if (node == here) {
				break;
			}
		}

		//정점이 두개 이상 있어야 사이클
		if (cycle_node.size() > 1) {
			for (int i = 0; i < cycle_node.size(); i++) {
				cycle_check[cycle_node[i]] = 1;
			}
		}

	}

	return parent;
}

//bfs를 통해 각 정점에서 사이클이 있는 정점까지 거리 구하기
int bfs(int start) {
	queue<int> q;
	vector<int> discovered(3005, -1);

	q.push(start);
	discovered[start] = 0;

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

		//사이클에 속한 정점에 도착했을때
		if (cycle_check[here] == 1) {
			return discovered[here];
		}

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];

			if (discovered[there] == -1) {
				q.push(there);
				discovered[there] = discovered[here] + 1;
			}
		}

	}

	return -1;
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int u, v;

		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(1, -1);

	for (int i = 1; i <= n; i++) {
		int dist = bfs(i);
		result.push_back(dist);
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}