[백준] 알고리즘 분류(트리,JAVA)15900번, 나무 탈출

문제 링크

15900번: 나무 탈출

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 성원이는 항상 먼저 턴을 시작합니다.

2. 루트 노드는 1번으로 고정이며 게임말이 루트 노드일 때 제거됩니다.,

3. 리프 노드에 게임말이 놓여집니다.

4. 각 턴에는 게임말을 부모 노드로 옮깁니다.

5. 성원이가 게임을 진행하여 이길 수 있는지 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

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

 

2. DFS탐색으로 리프 노드들의 깊이를 구해서 모두 더합니다.

 

3. 성원이가 게임을 이기는지 확인하여 결과를 출력합니다.

 

 

예제입력 2.

 

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

 

N : 4

 

1 2

2 3

3 4

 

 

2. DFS탐색으로 리프 노드들의 깊이를 구해서 모두 더합니다.

 

DFS탐색.

리프 노드는 1개 : 4번 노드

 

리프 노드 깊이의 합 : 3

 

3. 성원이가 게임을 이기는지 확인하여 결과를 출력합니다.

 

성원이와 형섭이는 턴을 돌아가면서 진행되기 때문에 성원이의 턴을 진행한 뒤에 게임말이 존재하지 않아야 합니다.

 

리프 노드에서 루트 노드의 길이가 홀수일 때 성원이가 이길 수 있습니다.

 

리프 노드에서 루트 노드의 길이가 짝수일 때는 형섭이가 이깁니다.

 

이 예제에서는 리프 노드 깊이의 합이 홀수(3)이기 때문에 Yes가 출력됩니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리의 노드 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 리프 노드의 깊이의 합을 구하였습니다.
• 깊이의 합이 홀수이면 Yes, 짝수이면 No을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 DFS탐색을 통해 리프 노드에 대한 깊이를 구해서 totalDepth에 더합니다.

 

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


public class Main {
    //트리 정보 관련 리스트
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static int totalDepth = 0;	//리프 노드 깊이의 합 저장하는 변수
    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));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0;i<=N;i++)
            tree.add(new ArrayList<>());
        //노드의 관계 저장
        for(int i=1;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }
        search(0, 1, 0);		//DFS탐색으로 리프 노드 깊이의 합 구하기
        if(totalDepth%2==1)		//홀수 일 때, 성원 승!
            bw.write("Yes");
        else		//짝수 일 때, 형섭 승!
            bw.write("No");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DFS탐색으로 리프 노드의 깊이를 구하는 함수
    static void search(int depth, int cur, int parent){
        boolean check = false;	//리프 노드 확인 변수
        //자식 노드 존재시 탐색
        for(int next : tree.get(cur)){
            if(parent != next){
                check = true;
                search(depth+1, next, cur);
            }
        }
        //리프 노드일 때 깊이 더하기
        if(!check)
            totalDepth += depth;
    }
}