[백준] 알고리즘 분류(트리,JAVA)6416번, 트리인가?

문제 링크

6416번: 트리인가?

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 비어있는 것도 트리의 만족합니다.

2. 루트 노드를 제외한 노드는 하나만 들어오는 간선이 존재합니다.

3. 루트에서는 다른 모든 노드로 이동할 수 있어야한다.

4. 트리에 대한 간선 정보가 주어질 때 트리의 형태가 맞는지 결과를 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 트리 구성 및 트리의 조건에 맞는지 확인합니다.

 

3. 트리의 조건에 만족여부에 따른 결과를 출력합니다.

 

트리의 조건.

 

1. 루트 노드가 1개이다.

모든 노드에서 들어오는 간선이 존재하지 않는 노드가 1개인지 확인한다.

0개이거나 1개보다 클 때 : 트리 X

1개 : 트리 조건 O

 

2. 루트 노드에서 다른 모든 노드로 이동이 가능해야 한다.

루트 노드에서 BFS탐색으로 다른 모든 노드들에 방문하는지 확인합니다.

모든 노드 방문하지 못할 때 : 트리 X

모든 노드 방문 : 트리 조건 O

 

3. 루트 노드를 제외한 노드는 들어오는 간선이 1개이다.

HashSet을 이용하여 들어오는 간선이 중복되는지 확인합니다.

중복 : 트리x

중복되지 않으면 : 트리 조건 O

 

4. 노드끼리 이동할 때 사이클이 만들어지지 않는다.

BFS탐색시 방문하는 노드를 다시 방문하는지 확인합니다.

다시 방문 시 : 사이클 존재, 트리 X방문 없을 때 : 사이클 없음, 트리 조건 O

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

※테스트 케이스 3번이 진행되는 과정을 보여드리겠습니다.

 

3 8  6 8  6 4
5 3  5 6  5 2  0 0

 

2. 트리 구성 및 트리의 조건에 맞는지 확인합니다.

 

트리 구성.

자식 노드.

2	{ }
3	{ 8 }
4	{ }
5	{ 3, 6, 2 }
6	{ 4, 8}
8	{ }

 

트리의 조건 확인.

 

1) 루트 노드가 1개이다.

들어오는 간선이 존재하는 노드 : 3, 6, 2, 8, 4

들어오는 간선이 존재하지 않는 노드 : 5

루트 노드 : 5

 

2) 루트 노드에서 다른 모든 노드로 이동이 가능해야 한다.

BFS탐색

루트 노드 5에서 시작해서 다른 모든 노드로 이동이 가능합니다.

 

3) 루트 노드를 제외한 노드는 들어오는 간선이 1개이다.

들어오는 간선이 0개인 노드 : 5

들어오는 간선이 1개인 노드 : 3, 6, 2, 4

들어오는 간선이 2개인 노드 : 8

들어오는 간선이 2개인 노드가 존재하기 때문에 트리의 조건X

 

 

 

3. 트리의 조건에 만족여부에 따른 결과를 출력합니다.

 

트리의 조건 3번에 만족하지 않기 때문에

"Case 3 is not a tree" 결과로 출력됩니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리의 정보를 띄어쓰기 기준 나누었습니다.
• 트리를 구성한 뒤 트리의 조건에 맞는지 확인합니다.
• 트리의 조건이 만족여부에 따른 결과를  BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• treeAdd함수는 트리의 노드를 저장하는 함수입니다. 
• rootSearch함수는 트리의 루트 노드를 구하고 2개 이상인지 확인합니다.
• bfs함수는 BFS탐색을 루트노드에서 다른 노드를 탐색하며 중복 방문하는지 확인합니다.
• setVisitedHash함수는 BFS에 사용할 방문 확인 HashMap을 초기화합니다.
• visitedCheck함수는 BFS탐색 후 모든 노드가 방문하였는지 확인합니다.

※결과를 출력할 때 글자 잘 확인하세요! 저는 is를 in으로 쓰고 왜 틀리는지 30분동안 찾고 있었습니다. ㅠ^ㅠ

 

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


public class Main {
    static HashMap<Integer, ArrayList<Integer>> tree;	//트리 정보
    static HashSet<Integer> check;	//들어오는 간선이 존재하는 노드
    static HashMap<Integer, Boolean> visited;	//BFS탐색으로 방문하는 노드 확인
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int index = 1;
        //각 테스트케이스 진행
        while(true){
            String str = br.readLine();
            if(str.equals("-1 -1"))		//테스트 종료
                break;
            else if(str.equals(""))		//다음 테스트 케이스 이동
                continue;
            else if(str.equals("0 0")){		//비어있는 트리일 때
                bw.write("Case " + index + " is a tree.\n");
                index++;
                continue;
            }
            boolean treeCheck = true;
            tree = new HashMap<>();
            check = new HashSet<>();
            //현재 테스트 케이스 트리 구성.
            while(true){
                boolean caseCheck = false;
                st = new StringTokenizer(str, " ");
                while(st.hasMoreTokens()) {
                    int u = Integer.parseInt(st.nextToken());
                    int v = Integer.parseInt(st.nextToken());
                    if (u == 0 && v == 0) {
                        caseCheck = true;
                        break;
                    }
                    //들어오는 간선이 2개이상인 경우.(트리 조건3.)
                    if (check.contains(v))
                        treeCheck = false;

                    check.add(v);
                    treeAdd(v);
                    treeAdd(u);
                    tree.get(u).add(v);
                }
                if(caseCheck)
                    break;
                str = br.readLine();
            }
            //트리의 조건 확인.
            if(treeCheck){
                int root = rootSearch();
                //트리의 조건1, 2, 4이 만족하는지 확인
                if(root == -1 || !bfs(root) || !visitedCheck()){
                    bw.write("Case " + index + " is not a tree.\n");
                }else		//트리의 조건 모두 만족.
                    bw.write("Case " + index + " is a tree.\n");
            }else	//트리의 조건 3번 만족하지 않음
                bw.write("Case " + index + " is not a tree.\n");
            index++;
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //트리의 노드 추가
    static void treeAdd(int key){
        if(!tree.containsKey(key))
            tree.put(key, new ArrayList<>());
    }
    //루트 노드 찾기
    static int rootSearch(){
        int root = -1;
        for(int key : tree.keySet()){
            if(!check.contains(key)){
                //루트 노드의 형태가 2개 이상일 때
                if(root != -1)
                    return -1;
                root = key;
            }
        }
        return root;
    }
    //BFS탐색으로 중복 방문 확인하는 함수
    static boolean bfs(int root){
        Queue<Integer> q = new LinkedList<>();
        setVisitedHash();
        visited.put(root, true);
        q.add(root);
        while(!q.isEmpty()){
            int cur = q.poll();
            //트리 인접 노드 탐색
            for(int next : tree.get(cur)){
                //트리 중복 방문일 때
                if(visited.get(next))
                    return false;
                visited.put(next, true);
                q.add(next);
            }
        }
        return true;
    }
    //방문 확인 HashMap 초기화하는 함수
    static void setVisitedHash(){
        visited = new HashMap<>();
        for(int key : tree.keySet()){
            visited.put(key, false);
        }
    }
    //모든 노드를 방문하였는지 확인하는 함수
    static boolean visitedCheck(){
        for(int key : visited.keySet()){
            //방문하지 못한 노드가 존재할 때
            if(!visited.get(key))
                return false;
        }
        return true;
    }
}