백준 15900 나무 탈출 java

solved.ac = 실버 1

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

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<Integer>[] 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. 전체 코드