<Algorithm> 63. 11266번 단절점
by BFine반응형
11266번 단절점
- DFS Spanning Tree 알고리즘과 그에 대한 활용할 수 있는 지에 대한 문제
- 단절점의 특징을 이해하는데 다소 시간이 많이 걸렸다. 처음에는 단순히 DFS로 모든 경우를 탐색했는데 시간초과가 발생했다.
- Spanning Tree는 순서와 루트 체크를 위해 필요했고 기존 그래프를 계속 사용되는 것을 생각해주어야 한다.
- Spanning Tree로 탐색하면서 방문한 정점의 인접 정점 중 하나라도 방문한 정점의 이전 순서의 정점로 갈 수 있을 경우 단절점아니다.
- 이때 이전순서는 Spanning Tree로 탐색하는 경우가 되고 이전순서로 가는 것을 확인하는 경우는 기존 그래프를 이용해야 한다.
|
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
96
97
98
99
100
101
102
103
104
105
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int count = 1;
static int[] discovered;
static boolean[] isCutVertax;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken())+1;
int M = Integer.parseInt(st.nextToken());
ArrayList<Node>[] aLists = new ArrayList[N];
discovered = new int[N];
isCutVertax = new boolean[N];
for(int i = 0; i < N; i ++) {
aLists[i] = new ArrayList<>();
}
for(int i = 0; i < M; i ++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
aLists[a].add(new Node(b));
aLists[b].add(new Node(a));
}
for(int i = 1; i < N ;i ++) {
if(discovered[i] == 0) {
dfs(i, true, aLists);
}
}
int cnt = 0;
for(int i = 1; i < N ; i++) {
if(isCutVertax[i]) {
cnt++;
}
}
System.out.println(cnt);
for(int i = 1; i < N ; i++) {
if(isCutVertax[i]) {
System.out.print(i +" ");
}
}
}
private static int dfs(int vertax, boolean root, ArrayList<Node>[] aLists) {
/* 자기보다 앞에 탐색할수 있는 경우가 있으면 단절점이 되지 않는다. */
/* DFS스패닝트리를 만들면서 기존 트리는 그대로 사용됨 없어지는 것이 아님*/
/* DFS스패닝 트리의 역할은 순서를 지정해 주는 것과
* DFS스패닝 트리에서 루트가 자식을 2개 가지는지 체크 */
discovered[vertax] = count++;
int ret = discovered[vertax];
// 자기랑 인접노드 중에서 가장 빨리 방문되는 노드의 순서를 저장하는 변수
int child = 0; // 루트 노드일 경우 스패닝트리에서 자식수
for(Node no: aLists[vertax]) {
if(discovered[no.adjVertax] == 0) {
child ++;
int low = dfs(no.adjVertax, false, aLists);
// 자식 노드가 갈수 있는 노드중 가장 일찍 방문한 노드
// 중간에 dfs 한다는 것은 정점의 끝까지 간다는 것을 의미
if(!root && low >= discovered[vertax]) {
isCutVertax[vertax] = true;
}// low가 자기의 순서보다 늦거나 같은 경우는
//즉 자기보다 앞에 있는 경로는 자기를 통해서 밖에 못간다. 단절점
ret = Math.min(ret, low);
}else {
ret = Math.min(ret, discovered[no.adjVertax]);
// 이미 방문한 정점과 ret값 비교 최소값 저장
}
}
if(root && child >= 2) {
isCutVertax[vertax] = true;
}// 루트는 위의 방법으로 확인할 수가 없기 때문에 스패닝 트리에서
// 자식이 두개 있다는 것은 단절점이다.
return ret;
}// dfs에서 다른 노드 값을 얻고 싶을때 return 아래에 사용
}
class Node{
int adjVertax;
public Node(int adjVertax) {
super();
this.adjVertax = adjVertax;
}
}
|
|
cs |
출처 : http://bowbowbow.tistory.com/3, http://jason9319.tistory.com/119
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 65. 14675번 단절점과 단절선 (0) | 2018.08.25 |
|---|---|
| <Algorithm> 64. 11400번 단절선 (0) | 2018.08.24 |
| <Algorithm> 62. 11403번 경로찾기 (0) | 2018.08.22 |
| <Algorithm> 61. 2357번 최대값과 최소값(Segment Tree) (0) | 2018.08.22 |
| <Algorithm> 60. 2042번 구간 합 구하기 (0) | 2018.08.21 |
블로그의 정보
57개월 BackEnd
BFine