6416번: 트리인가?
트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다.
www.acmicpc.net
자바라서 입력 받는거부터 좀 힘들었습니다..
다행히 검색으로 다음 토큰이 있는지 확인하는 st.hasMoreTokens() 라는 것을 찾아서 입력을 받았습니다.
이 문제는 u v 로 입력이 주어지고 이는 u->v를 뜻합니다.
트리이기 때문에 방향 그래프이고 한 방향으로만 향합니다. 즉, v->u는 안됩니다.
이 문제에서는 트리가 아닌 조건들을 모두 체크해주어야합니다.
1. 부모노드가 2개 이상인지
2. 루트노드가 1개가 아닌지 (0개이거나 2개 이상인지)
3. 사이클이 있는지
먼저 1번, 부모노드 확인입니다.
입력을 받으면서 자식으로 등록되는 노드(v)들을 Set을 이용하여 저장했고, 만약에 Set에 있는 값을 다시 넣게 된다면 자식으로 등록이 두번 됩니다. 즉 부모노드가 2개이상이 된다는 뜻입니다. => not tree
2번, 루트노드 확인입니다.
입력으로 주어지는 모든 부모노드(u)를 Set을 이용하여 저장했고, 만약에 Set에 있는 원소 중에 자식으로 등록되어있지 않으면 루트노드입니다.
만약 이러한 노드가 없거나 2개 이상이면 not tree입니다.
3번, 사이클 확인입니다.
map을 이용하여 Key는 부모노드(u), Value는 자식노드들(v)을 Integer, ArrayList<Integer>로 구현하였습니다.
사이클 확인은 dfs로 순회하여 next가 이미 방문한 노드인지 확인하였고, 이미 방문한 노드면 사이클이 있다는 말이기 때문에 not tree입니다.
3번의 확인이 끝나고 셋 다 아니라면 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Map<Integer, ArrayList<Integer>> m = new HashMap<>();
static Set<Integer> findRoot = new HashSet<>();
static Set<Integer> child = new HashSet<>();
static Set<Integer> visit = new HashSet<>();
static boolean tworoot, twoparents, cycle;
static int u, v, root;
static void dfs(int x) {
visit.add(x);
ArrayList<Integer> graph = m.get(x);
if (graph == null)
return;
for (int i = 0; i < graph.size(); i++) {
int next = graph.get(i);
if (visit.contains(next)) {
cycle = true;
return;
}
dfs(next);
if (cycle)
return;
}
}
static void rootFinding() {
Iterator<Integer> iter = findRoot.iterator();
while (iter.hasNext()) {
int x = iter.next();
if (!child.contains(x)) {
if (root != 0) {
tworoot = true;
return;
}
root = x;
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
while (true) {
while (!st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
if (u == 0 || u == -1)
return;
if (m.containsKey(u)) {
m.get(u).add(v);
} else {
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(v);
m.put(u, tmp);
}
if (child.contains(v))
twoparents = true;
else
child.add(v);
findRoot.add(u);
}
}
static void clear() {
m.clear();
findRoot.clear();
child.clear();
visit.clear();
twoparents = false;
tworoot = false;
cycle = false;
root = 0;
}
public static void main(String[] args) throws Exception {
for (int T = 1;; T++) {
input();
if (u == -1)
break;
sb.append("Case " + T + " is ");
if (child.isEmpty()) {
sb.append("a tree.\n");
continue;
}
if (twoparents) {
sb.append("not a tree.\n");
clear();
continue;
}
rootFinding();
if (root == 0 || tworoot) {
sb.append("not a tree.\n");
clear();
continue;
}
dfs(root);
if (cycle)
sb.append("not a tree.\n");
else
sb.append("a tree.\n");
clear();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 1935 후위 표기식2 (0) | 2021.02.05 |
|---|---|
| boj 2493 탑 (0) | 2021.02.04 |
| boj 3190 뱀 (0) | 2021.02.02 |
| boj 2346 풍선 터뜨리기 (0) | 2021.02.02 |
| boj 5397 키로거 (0) | 2021.02.02 |