백준 16947. 서울 지하철 2호선
알고리즘 기초 문제 중 601 - 그래프1(연습)
1. 간단 설명
지하철 노선도는 순환선과 지선으로 나눌 수 있다
순환선 : 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선
지선 : 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선
즉 순환선은 사이클이고, 지선은 사이클에서 뻗어나온 트리
그래프에서 사이클을 찾고, 각 노드들과 이 사이클간의 거리를 구하는 문제
2. 예시
예제 1
1
2
3
4
5
4
1 3
4 3
4 2
1 2
1
2
3
1 - 3
| |
2 - 4
와 같은 순환선이므로, 모든 역은 순환선으로부터의 거리가 0이다
예제 2
1
2
3
4
5
6
7
6
1 2
3 4
6 4
2 3
1 3
3 5
1
2
3
4
1 - 2
ㄴ 3 - 4 - 6
|
5
1-2-3은 순환선이고, 4와 5는 거리가 1, 6은 거리가 2인 지선이다
3. 알고리즘
크게 두 파트로 나눌 수 있다
순환선을 찾는 부분
찾은 순환선과의 거리를 구하는 부분
순환선을 찾는 부분은 깊이 우선 탐색(DFS)를 통해서
깊이가 3이상이고, 시작점과 같은지를 비교하여 찾을 수 있다
예를들어 A - B - C - A 순환선이 있다면
A에서 A로 돌아왔을때 깊이는 3, 시작점인 A와 도착점인 A가 같으므로 순환선이다
A-B-A라면, 그냥 두 역이 연결되어있는것이므로 순환선이 아니다. 깊이는 3을 초과해야함
찾은 순환선과의 거리를 구하는 부분은
순환선의 역 번호를 기록해두고, 이를 너비 우선 탐색(BFS)를 돌린다
해당 역과 연결된 역들을 거리를 1씩 증가 시켜가면서, 모든 역을 탐색한다
1
2
3
4
5
6
7
8
1. N과 엣지 정보 정보 입력받기
2. 1번 역부터 시작하여 그래프에서 각 노드를 탐색하면서, 사이클을 찾는다
2-1. 역을 탐색하면서, 이전 역의 정보를 저장한다
2-2. 사이클을 찾았다면, DFS를 종료한다.
- 사이클 정보는 visited에 저장되어있다
3. 사이클을 찾았다면, 이 사이클에 속한 노드들을 큐에 넣는다
4. 큐를 BFS를 돌려 각 노드의 거리를 기록한다
5. 기록된 거리를 출력한다
필요 변수
역의 개수 int N(3 ≤ N ≤ 3,000)
그래프 연결 정보 vector< vector<int> > edge
- 사이클을 찾는데 필요한 변수들
DFS를 사용할 것이므로 관련 변수들 필요
각 역에 방문했는지 체크할 int visited[3001] : 역에 방문하면서 어떤 역에서 왔는지를 기록해둔다
사이클을 찾았는지 기록할 플래그 bool cycle_found
- 각 역의 거리를 찾는데 필요한 변수들
BFS 탐색용 queue< pair<int, int> > qu;
BFS 탐색 동안 방문 여부 체크 및 거리를 기록할 int dist[MAX];
4. 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <queue>
#define MAX 3001
using namespace std;
int N;
vector< vector<int> > edge;
int visited[MAX];
int dist[MAX];
bool cycle_found = false;
void input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
edge.resize(N + 1);
for (int i = 0; i < N; i++) {
int start, end; cin >> start >> end;
edge[start].push_back(end);
edge[end].push_back(start);
}
}
void DFS(int level, int start, int node) {
if (cycle_found == true) return;
if (level > 2 && start == node) { // 3개 이상 지나왔고, 첫 노드와 현재 노드가 같다면 사이클임
cycle_found = true;
return;
}
// 현재 역과 연결된 역들 탐색
for (int i = 0; i < edge[node].size(); i++) {
int next = edge[node][i];
if (visited[next] != 0) continue; // 이미 방문한 역이면 패스
visited[next] = node; // 다음역 방문처리. 어느역에서 왔는지 기록
DFS(level + 1, start, next); // 다음역으로 이동
if (cycle_found == true) return; // 순환선을 찾은경우 visited에는 순환선 정보가 담겨있음
visited[next] = 0; // 초기화
}
}
void BFS() {
queue< pair<int, int> > qu;
// 순환선에 속하는 역들을 큐에 넣음
for (int i = 1; i <= N; i++) {
if (visited[i] != 0) {
qu.push({ i, 1 });
dist[i] = 1; // 순환선들은 모두 방문표시 해둠
}
}
while (!qu.empty()) {
pair<int, int> now = qu.front();
qu.pop();
int cur_node = now.first;
int dis = now.second;
// 현재 노드와 연결된 노드 탐색
for (int i = 0; i <edge[cur_node].size(); i++) {
int next = edge[cur_node][i];
if (dist[next] != 0) continue; // 이미 방문한 노드
dist[next] = dis + 1;
qu.push({ next, dis + 1 });
}
}
}
int main() {
input();
// 1번 역부터, N번 역까지 돌면서 순환선 찾기
for (int i = 1; i <= N; i++) {
if (visited[i] == 0) {
DFS(0, i, i);
}
}
// 역은 모두 연결되어있으므로 1번 역만 살펴봐도 되지 않을까?
BFS();
for (int i = 1; i <= N; i++) {
cout << dist[i] - 1 << " "; // 거리를 1부터 시작했으므로 1씩 빼준다
}
return 0;
}
DFS와 BFS를 모두 사용하는 문제
두가지를 같이 사용하려하니 햇갈리는 부분이 많았다