[백준]6416: 트리인가? - JAVA

[백준]6416: 트리인가?

www.acmicpc.net/problem/6416

6416번: 트리인가?

풀이

간선에 대한 정보를 입력 받아 해당 간선과 정점으로 만들 수 있는 그래프가 트리인지 판별하는 문제였다.

 

트리인지 판별하는 과정은 다음과 같다.

1. 루트가 하나여야 한다.
2. 루트를 제외한 모든 노드들의 진입 간선은 한개여야 한다.
3. 정점의 개수 - 1 == 간선의 개수여야 한다.

 

정점의 개수를 중복 없이 세 주기 위해 HashMap을 사용하였다. key값을 정점 값으로, value값을 진입 간선의 개수로 사용해 주었다. map의 getOrDefault()함수를 사용하여 기존의 값을 가지고 연산을 해주었다.

 

이 문제에서 유의할 점은 간선, 정점이 하나도 없는 0, 0이 입력되어도 빈 트리이므로 트리 조건에 관계 없이 트리가 맞다는 출력문이 출력되어야 한다는 점이다. 그래서 map의 size가 0이면 트리라고 출력해 주도록 하였다.

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        HashMap<Integer, Integer> vertex; //정점의 개수를 센다
        int count = 1; //case의 순서를 센다
        
        while(true) {
            vertex = new HashMap<>();
            int edge = 0; //간선의 수
            while(true) {
                int start = scan.nextInt();
                int end = scan.nextInt();
                
                if(start == -1 && end == -1) return;
                else if(start == 0 && end == 0) break;
 
                vertex.put(start, vertex.getOrDefault(start, 0));
                vertex.put(end, vertex.getOrDefault(end, 0) + 1);
                edge++;
            }
            
            int root = 0;
            boolean isTrue = true;
            Iterator<Integer> key = vertex.keySet().iterator();
            while(key.hasNext()) {
                int num = key.next();
                if(vertex.get(num) == 0) root++;
                else if(vertex.get(num) > 1) {
                    isTrue = false;
                    break;
                }
            }
            
            if(vertex.size() == 0) {
                System.out.println("Case " + count + " is a tree.");
            }
            else if(isTrue && root == 1 && edge == vertex.size() - 1) {
                System.out.println("Case " + count + " is a tree.");
            } else {
                System.out.println("Case " + count + " is not a tree.");
            }
            count++;
        }
    }
}