[문제] 백준 15900번 나무 탈출

www.acmicpc.net/problem/15900

15900번: 나무 탈출

풀이

 

게임 진행 순서가 성원- 형석 - 성원 -형석 -...이므로 성원이는 짝수번 순서에 게임을 하고, 형석이는 홀수번 째에 게임을 한다. (0번부터 수를 센다고 했을 때)

 

따라서 leaf 노드들에서 root까지의 간선 합이 짝수가 되면 성원이는 지고, 홀수가 되면 이긴다.

 

처음 문제를 풀 때는 leaf 노드에서 시작해서 root까지 이동하면서 bfs 탐색했는데, 시간 초과였다.

그래서 root->leaf 노드들 까지 dfs 탐색하니 정답이 되었다!

public class BOJ_15900{
	static ArrayList<ArrayList<Integer>> list = new ArrayList<>();	//list의 list
	static boolean[] visited;	//노드 방문 체크
	static int sum = 0;	//모든 leaf노드들에서 root까지의 거리 합
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(in.readLine());	//노드 개수
		
		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<Integer>());	//init list
		}
        
		visited = new boolean[N+1];	//1번 based -> N+1 길이 만큼 배열 할당

		// 노드 간 연결
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
		
			list.get(a).add(b);	// 노드 간 연결
			list.get(b).add(a);
		}
        
		dfs(1,0);	// root => leaf까지 탐색
		
		if(sum%2 == 0) {				// leaf노드들에서 root까지의 거리합 짝수 : lose, 홀수: win
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}
	}
	//num: 노드 번호, d: 루트에서 leaf노드까지의 거리 축적
	static void dfs(int num, int d) {
		visited[num] = true;	
		for(int i:list.get(num)) {	//num번째 노드와 연결된 노드들 중
			if(!visited[i]) {	//부모노드는 이미 방문한 상태이므로, 방문 안한 노드가 자식노드임
				dfs(i,d+1);	//거리 1만큼 증가
			}
			
		}
		if(list.get(num).size() == 1) {	// 해당 노드가 leaf라면 연결된 노드는 부모노드 1개밖에 없음
			sum += d;	//leaf노드일 때 sum 축적
		}
	}
}