백준 15900 나무 탈출 java

백준 15900 나무 탈출 java

728x90

solved.ac = 실버 1

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

1. 접근

DFS로 접근시 인접 리스트를 사용하니 O(V + E) == O(500,000 + 499,999) = 1,000,000로 시간초과 없이 풀 수 있다!

게임의 규칙을 살펴보면 각 말단 노드의 개수 = 말의 수이며 한 턴에 한 번씩 현재 노드의 부모 노드로 이동한다.

또한 게임에서 이기려면 순서가 먼저인 성원이 차례에 마지막 말을 루트로 이동시켜야 한다.

예제 3번을 그림으로 보면

말단 노드인 5번 노드는 루트 노드까지 총 세 번을 이동해야 하며 문제로 비유하자면 세 턴을 필요로 한다.

모든 말단 노드에 대해 루트까지의 이동 거리를 보면

5 -> 6 -> 4 -> 1 = 3 (성원 - 형석 - 성원)

7 -> 4 -> 1 = 2 (형석 - 성원)

2 -> 3 -> 1 = 2 (형석 - 성원)

8 -> 1 = 1 (형석)

위의 경우는 총 8번의 턴이 소모되며 마지막 말을 이동시킨 형석이가 승리하게 된다.

즉, 이동거리가 홀수여야 성원이가 승리할 수 있다.

2. 풀이

변수세팅

static int N, cnt = 0; static ArrayList[] graph; public static void main(String[] args) throws IOException { N = Integer.parseInt(br.readLine()); graph = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); for (int i = 1; i < N; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } solution(); }

DFS 호출 및 정답 출력

static void solution() { DFS(1, -1, 0); // 성원이가 먼저 시작하니 이기려면 타고 올라가는 총 수가 홀수여야 한다. System.out.println((cnt % 2 == 0) ? "No" : "Yes"); }

DFS

static void DFS(int x, int parent, int depth) { // 연결된 간선이 하나 뿐이고 그 하나가 부모라면 그 노드는 말단 노드이다. if (graph[x].size() == 1 && graph[x].get(0) == parent) { // 타고 내려온 depth를 총 depth에 더한다. cnt += depth; return; } for (int y : graph[x]) { if (y == parent) continue; DFS(y, x, depth + 1); } }

3. 전체코드

728x90

from http://dhbang.tistory.com/30 by ccl(A) rewrite - 2021-12-15 22:00:34