[BOJ] 백준 6416번 트리인가? (Java)

#6416 트리인가?

난이도 : 골드 5

유형 : 트리

6416번: 트리인가?

▸ 문제

트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. 이때, 노드 u에서 노드 v로 가는 간선이 존재하면 간선을 u에 대해서는 '나가는 간선', v에 대해서는 '들어오는 간선'이라고 하자.

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

아래의 그림을 보자. 원은 노드, 화살표는 간선을 의미하며, 화살표의 방향이 노드 u에서 노드 v로 향하는 경우 이는 이 간선이 u에서 나가는 간선이며 v로 들어오는 간선이다. 3개의 그림 중 앞의 2개는 트리지만 뒤의 1개는 트리가 아니다.

 

당신은 간선의 정보들을 받아서 해당 케이스가 트리인지를 판별해야 한다.

▸ 입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 입력의 끝에는 두 개의 음의 정수가 주어진다.

각 테스트 케이스는 여러 개의 정수쌍으로 이루어져 있으며, 테스트 케이스의 끝에는 두 개의 0이 주어진다.

각 정수쌍 u, v에 대해서 이는 노드 u에서 노드 v로 가는 간선이 존재함을 의미한다. u와 v는 0보다 크다.

▸ 출력

각 테스트 케이스에 대해서, 테스트 케이스의 번호가 k일 때(k는 1부터 시작하며, 1씩 증가한다) 트리일 경우 "Case k is a tree."를, 트리가 아닐 경우 "Case k is not a tree."를 출력한다.

 

문제 풀이  

문제 개념은 쉬운데 입출력이랑 엣지케이스에서 시간을 많이 헤메었다. 솔직히 그렇게 좋은 문제는 아니지만 이러한 문제 또한 CP를 위해서라면 풀어보는 것도 나쁘지 않을 것 같다는 생각이 들었다. 

 

문제에서 주어진 대로 두 정점의 데이터(u, v)를 받아서 해당 그래프가 트리인지 아닌지 판별해주면 된다. 정점의 범위가 주어지지 않았기 때문에 배열을 사용하면 안된다. 그래서 해시 자료구조를 지닌 Map과 Set을 사용해서 풀이하였다.

 

설계

1. a → b의 방향으로 주어지는 데이터를 각각 상황에 맞춰 set과 map자료구조에 저장한다.
2. 간선을 저장하는 vertex(set)에는 b의 데이터를 저장한다.
   1. vertex에 중복되는 데이터가 들어간다면 해당 정점에 2개의 간선이 들어오므로 flag = true;
   2. if(vertex.size()=0), 간선의 갯수가 0개이면 그냥 트리로 취급한다.
3. 정점을 저장하는 map에는 a와 a가 잇고 있는 간선의 갯수를 저장한다.
4. map에 저장된 정점 중 vertex가 없는(들어오는 간선) 정점을 루트노드로 취급한다.
   1. if(rootNum!=-1), 만약 0개이거나 2개이상이면 트리가 아니므로 flag = true;
5. -1 -1이 나올때 까지 해당 과정(1~4)을 반복한다.

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		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;
		out : 
		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 out;
				
				if(!vertex.add(b)) { // 간선 2개이상 fail
					flag = true;
				}
				map.put(a, map.getOrDefault(a, 0)+1);
			}
            
			if(vertex.size()!=0) { // vertex 0인 경우 그냥 pass 
				int rootNum=0;
				for(int num : map.keySet()) {
					if(!vertex.contains(num)) rootNum++;
				}
				// root 1개 이상 or 0
				if(rootNum!=1) flag = true;
			}
			if(flag) {
				sb.append("Case " + (tc)+" is not a tree.\n");
			}else {
				sb.append("Case " + (tc)+" is a tree.\n");
			}
		}
		System.out.println(sb.toString());
	}
}