어흥
[백준 16947] 서울 지하철 2호선 (C++) 본문
문제 링크: www.acmicpc.net/problem/16947
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;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준 2886] 자리 전쟁 (C++) (0) | 2020.09.22 |
---|---|
[백준 4358] 생태학 (C++) (2) | 2020.09.19 |
[백준 2143] 두 배열의 합 (C++) (0) | 2020.09.08 |
[백준 13422] 도둑 (C++) (0) | 2020.09.08 |
[백준 14391] 종이 조각 (C++) (0) | 2020.09.05 |