[백준/BOJ] 백준 16947번 : 서울 지하철 2호선
2023. 10. 18. 17:02ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/16947
역들의 관계로 그래프를 만들고, 직전에 방문했던 위치는 방문하지 않는 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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 11049번 : 행렬 곱셈 순서 (1) | 2023.10.18 |
---|---|
[백준/BOJ] 백준 15758번 : Milking Order (1) | 2023.10.18 |
[백준/BOJ] 백준 22348번 : 헬기 착륙장 (1) | 2023.10.18 |
[백준/BOJ] 백준 14658번 : 하늘에서 별똥별이 빗발친다 (0) | 2023.10.18 |
[백준/BOJ] 백준 20440번 : 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (0) | 2023.10.18 |