문제
방향 간선들이 주어질 때, 해당 그래프가 트리인지 판별하라. 트리 조건: 루트가 정확히 1개, 루트를 제외한 모든 노드의 진입 차수가 정확히 1이다.
입력
간선 쌍이 주어지며, 0 0이면 케이스 종료, -1 -1이면 전체 종료이다.
출력
각 케이스마다 "Case k is a tree." 또는 "Case k is not a tree."를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 2 2 3 0 0 -1 -1 | Case 1 is a tree. |
풀이
간선 정보로 진입 차수와 루트 수를 확인하여 트리 조건을 검증한다.
- 각 간선의 도착 노드를
Set에 저장하여 진입 차수를 추적한다 - 같은 노드가 두 번 이상 도착 노드가 되면 트리가 아니다 (진입 차수 2 이상)
- 출발 노드 중 도착 노드에 없는 노드가 루트 후보이다
- 루트가 정확히 1개가 아니면 트리가 아니다
핵심 아이디어: 트리는 루트 1개 + 나머지 노드 진입 차수 1의 조건을 만족해야 한다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day742BOJ6416트리인가 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> vertex = new HashSet<>();
StringBuilder sb = new StringBuilder();
StringTokenizer st;
outer: for (int tc = 1;; tc++) {
map = new HashMap<>();
vertex = new HashSet<>();
boolean flag = false;
st = new StringTokenizer(br.readLine());
while (true) {
if (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (a == 0)
break;
if (a == -1)
break outer;
if (!vertex.add(b)) {
flag = true;
}
map.put(a, map.getOrDefault(a, 0) + 1);
}
if (vertex.size() != 0) {
int rootNum = 0;
for (int num : map.keySet()) {
if (!vertex.contains(num))
rootNum++;
}
if (rootNum != 1)
flag = true;
}
sb.append("Case " + (tc) + ((flag) ? " is not a tree.\n" : " is a tree.\n"));
}
System.out.println(sb.toString());
}
}복잡도
- 시간: O(N)
- 공간: O(N)