[백준 / BOJ] 15900 나무 탈출

문제

출처 : https://www.acmicpc.net/problem/15900

15900번: 나무 탈출

트리의 정점의 개수 N, N-1개의 줄에 거쳐 간선의 정보가 주어진다.

각 간선의 끝(리프노드)에 게임 말이 존재한다.

 

성원이와 형석이는 이 게임 말을 한턴에 한번씩 부모노드로 움직이는 방식으로 게임을 진행하려고한다.

게임 말은 루트노드에 도착하면 사라지며, 이 과정을 반복하다 자신의 턴에 더 이상 고를수있는 게임 말이 없다면, 그 사람은 게임에서 패배한다.

 

항상 성원이가 먼저 시작할때, 성원이가 게임에 승리할 수 있는지 없는지 구하는 프로그램을 만드는 문제다.

 

 

---

풀이

"항상 최적의 선택"이라는 말을 보고 DP 게임이론 문제인가? 라고 의심을 했는데, 매 턴마다 무조건 한칸 위(부모 노드)로 움직여야 하므로 기본 트리탐색으로도 풀리는 문제다.

 

풀이는 간단하다.

- 모든 게임 말이 루트 노드까지 이동하기 위한(게임말과 루트노드 사이의), 거리 를 구한다. 이 거리가 짝수라면 항상 이길수없고, 홀수라면 항상 이길수있다.

 

주요 소스코드

	private void setNodeDistance(int idx, int distance){
		check[idx] = true;
		if(tree.get(idx).size() == 1 && idx != 1) dis += distance;
		for(int i = 0; i < tree.get(idx).size(); i++){
			if(check[tree.get(idx).get(i)]) continue;
			setNodeDistance(tree.get(idx).get(i), distance+1);
		}
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/15900%20%EB%82%98%EB%AC%B4%20%ED%83%88%EC%B6%9C/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃