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

2023. 10. 18. 17:02알고리즘 문제풀이

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

 

16947번: 서울 지하철 2호선

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호

www.acmicpc.net

 

역들의 관계로 그래프를 만들고, 직전에 방문했던 위치는 방문하지 않는 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;
}