[백준 - Java] 15900번 : 나무 탈출

틀렸습니다!!!

나는 결국 다른 사람들의 풀이를 보고 문제를 해결했다ㅠㅠ

처음에 A가 고르고, B가 고르고 모든 경우를 다 따지고, 부모 노드로 바꿨다가. 노드를 삭제했다가 별별일을 다 하다

너무 시간이 오래 걸려서 포기함...

 

답을 봤더니 너무 허망했음ㅋㅋㅋㅋ역시 사람은 머리를 잘 굴려야함!

풀이는 아래에!!

 

* 아 참 Scanner로 입력받으면 시간 초과!!!!

문제

www.acmicpc.net/problem/15900

15900번: 나무 탈출

설명

게임은 리프 노드부터 시작되고, 리프 노드는 부모 노드로만 이동한다.

이와 같은 방식으로 게임을 진행해 결국 루트 노드까지 모든 리프 노드가 이동한다면 게임이 끝나는 방식.

 

즉 게임 말은 리프 노드부터 루트 노드까지 이어지는 한 줄의 길로만 이동한다는 것이다!

 

이를 생각해보면 어떤 경우가 성원이가 이길 수 있을까?

 

 

 

문제의 예제 3을 그림으로 나타내 보면 위와 같다.

 

예를 들어 1, 4 정점으로만 이루어진 트리의 경우 4를 성원이가 옮기고, 형섭이가 1, 성원이는 옮길 말이 없기에 패배한다.

하지만 1, 4, 7 정점으로만 이루어진 트리의 경우 7을 성원이가 옮기고, 형섭이가 1, 성원이가 1을 옮기면 승리하게 된다.

 

즉, 루트 노드에서 리프 노드까지의 깊이 합이 짝수라면 성원이가 패배하고, 홀수면은 승리한다는 것이다.

풀이

위의 로직을 바탕으로 먼저 인접 리스트를 사용해 트리를 표현한다.

그리고 루트 노드에서 리프 노드까지의 깊이 합을 구하기 위해 DFS를 사용한다.

DFS내에서 리프 노드에 도달한다면 깊이를 다 구한 것이므로 그때의 깊이를 결과 변수에 저장해 깊이의 합을 구한다.

리프 노드는 자식 노드가 존재하지 않기 때문에 인접 리스트의 사이즈가 1이면 리프 노드임을 알 수 있다.

전체 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static LinkedList<Integer>[] adjList;
	public static int answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		adjList = new LinkedList[N+1];

		for (int i = 1; i <= N; i++) {
			adjList[i] = new LinkedList<Integer>();
		}

		for(int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			adjList[a].add(b);
			adjList[b].add(a);
		}

		dfs(1, 0, 0);
		
		System.out.println((answer % 2) == 0 ? "No" : "Yes");
		
		br.close();
	}

	public static void dfs(int cur, int p, int cnt) {
		for(int next : adjList[cur]) {
			if(next != p) {
				dfs(next, cur, cnt+1);
			}
		}
		
		if(adjList[cur].size() == 1) {
			answer += cnt;
		}
	}

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2315900/src/Main.java

KwonMinha/BOJ