[Baekjoon] 15900_나무 탈출

Silver I

문제(출처: https://www.acmicpc.net/problem/15900)

---

< 나무 탈출 >

 

문제 풀이 

 

루트 노드에서 dfs를 활용해서 모든 정점을 방문한다. 리프 노드에 도달한 경우 depth를 구해 더해준다.

모든 리프 노드에 도달했을 때 depth의 합이 홀수이면 게임에서 이길 수 있으며 짝수이면 게임에서 이길 수 없다.

 

 my solution (Java)

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

public class _15900_ { // 나무 탈출
	static ArrayList<ArrayList<Integer>> arr;
	static int cnt;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		arr = new ArrayList<>();
		visited = new boolean[n + 1];
		for (int i = 0; i < n + 1; i++) {
			arr.add(new ArrayList<>());
		}

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

			arr.get(a).add(b);
			arr.get(b).add(a);

		}

		cnt = 0;
		dfs(1, 0);

		if (cnt % 2 == 0)
			System.out.println("No");
		else
			System.out.println("Yes");
	}

	private static void dfs(int idx, int depth) {
		visited[idx] = true;
		int check=0;
		for (int i = 0; i < arr.get(idx).size(); i++) {
			if (visited[arr.get(idx).get(i)]) {
				check+=1;
				continue;
			}
			dfs(arr.get(idx).get(i), depth + 1);
		}
		if(check==arr.get(idx).size()) {
			cnt += depth;
			return;
		}
	}
}

 

Main

변수)
n : 트리의 정점 개수
arr : 트리 정보
visited : 방문 여부
cnt : 모든 리프 노드에 도달할 때 depth의 합

 

-트리의 정점 개수(n) 입력

- 트리의 간선 정보를 입력받아 저장 (arr)

- dfs 함수 호출

- cnt가 홀수라면 게임에서 이기고 짝수이면 게임에서 짐

 

dfs

- 트리 정점 방문 표시

- 정점과 연결된 정점 중에서 방문하지 않은 곳이 있다면 dfs 함수 호출

- 정점과 연결된 정점 중에서 모두 다 방문한 곳이라면 리프노드란 뜻이므로 depth를 더해줌

---

---