백준 6416 : 트리인가 풀이 (Java)

www.acmicpc.net/problem/6416

6416번: 트리인가?

울화통의 흔적

참고한 코드

velog.io/@pss407/%EB%B0%B1%EC%A4%806416-%ED%8A%B8%EB%A6%AC%EC%9D%B8%EA%B0%80

[백준]#6416 트리인가?

Key Point

0. 먼저, 이 문제는 결국 내 힘으로 풀지 못했다. 풀이법에서는 틀린 게 없는 것 같은데, 아직 Java 가 익숙하지 않아서 코드를 잘못 짠 것인지 모르겠는데 질문 검색 에서의 케이스들도 다 맞아서 반례를 못 찾았다 결국...

1. 이 문제의 핵심은,

"루트가 하나인지", "정점 갯수 - 간선 갯수 == 1인지", "들어오는 간선의 갯수가 2개 이상인 노드가 있는지"

이다.

2. 정점이 순서대로 들어오지 않으므로, HashSet 을 이용해서 중복을 제거하면서 넣으면 그것이 정점이 된다.

3. 이건 세세한 건데, 문장의 마지막에 점 찍는 거 잊지 말자.

 

소스코드

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<Integer> set;
        int[] cnt; // idx : 노드 번호 value : 들어오는 간선 의 갯수
        int tc = 0;
        int root;
        boolean hasTwoMoreIncomeVector;
        int v; // 간선의 갯수

        while(true) {
            set = new HashSet<>();
            cnt = new int[1001];
            root = 0;
            tc++;
            hasTwoMoreIncomeVector = false;
            v = 0;

            while(true) {
                int a = sc.nextInt();
                int b = sc.nextInt();

                if (a == 0 && b == 0) break;
                if (a == -1 && b == -1) return;

                set.add(a);
                set.add(b);
                cnt[b]++;
                v++;
            }
            if(set.size()==0) {
                System.out.println("Case "+ tc +" is a tree."); // 아무 것도 없는 트리도 트리임.
                continue;
            }

            Iterator iter = set.iterator();
            while(iter.hasNext()) {
                int num = (int)iter.next();
                if(cnt[num]==0) root++; // 들어오는 간선의 갯수가 0인 경우 root
                if(cnt[num]>1) {
                    hasTwoMoreIncomeVector = true; // 들어오는 간선의 갯수가 2개 이상인 노드가 있는 경우
                    break;
                }
            }

            if(hasTwoMoreIncomeVector || root!=1 || set.size()-v!=1) // 들어오는 간선의 갯수가 2개 이상 or 루트 노드가 유일하지 않음 or 노드의 개수 - 간선의 개수 가 1이 아님
                System.out.println("Case "+ tc +" is not a tree.");

            else
                System.out.println("Case "+ tc +" is a tree.");
        }
    }
}