[백준] 14570번 나무위의구슬

문제 설명

• https://www.acmicpc.net/problem/14570
• Gold 1

문제 풀이

• 단순 시뮬레이션 혹은 DFS 문제이다.

• 문제에서 K값은 매우 크므로 한개씩 시뮬레이션은 불가하다.

• 문제에서 K개 구슬이 특정 노드에 도착했을 때 시나리오는 다음과 같다.

  1. 자식 노드가 없을때 -> 해당 노드에 멈춤
  2. 자식 노드가 1개일 때 -> 해당 자식으로 이동
  3. 자식 노드가 2개 일 때
     3-1) K % 2 == 1인 경우 -> 왼쪽 자식으로 K/2 + 1개 이동
     3-2) K % 2 == 0인 경우 -> 오른쪽 자식으로 K/2개 이동

• 위 시나리오대로 while문이나 dfs로 구현하면 된다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Node {
        int n;
        Node l, r;

        public Node(int n, Node l, Node r) {
            this.n = n;
            this.l = l;
            this.r = r;
        }
    }
    static int N;
    static long K;

    static Node[] tree;


    static void solve() throws IOException {
        int cur = 1;
        long remain = K;
        while(true) {
            // 1. 자식 노드가 없다면 해당 노드에 멈춤
            if (tree[cur].l == null && tree[cur].r == null) {
                bw.write(cur + "\n");
                break;
            }

            // 2. 한쪽 자식 노드만 있다면 해당 노드로 이동
            if ((tree[cur].l == null && tree[cur].r != null)
                || (tree[cur].l != null && tree[cur].r == null)) {
                cur = tree[cur].l == null ? tree[cur].r.n : tree[cur].l.n;
                continue;
            }

            // 3. 자식이 둘 다 존재하는 경우

            // 3-1) 왼쪽 자식 노드로 이동
            if (remain % 2 == 1) {
                cur = tree[cur].l.n;
                remain = remain/2 + 1;
            }
            // 3-2) 오른쪽 자식 노드로 이동
            else {
                cur = tree[cur].r.n;
                remain = remain/2;
            }

        }
        bw.flush();
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        tree = new Node[N + 1];
        for (int i = 1; i <= N; i++)
            tree[i] = new Node(i, null, null);
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (a != -1) tree[i].l = tree[a];
            if (b != -1) tree[i].r = tree[b];
        }
        K = Long.parseLong(br.readLine());
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * - 자식이 없으면 멈춘다.
 * - 자식이 1개면 해당 자식으로 이동
 * - 자식이 2개면 구슬의 합이 적은 쪽으로 떨어진다. 같으면 왼쪽
 * - K번째 구슬이 어느 노드에서 멈출까
 *
 * N
 * n개의 노드 정보 (U, V)
 * K
 *
 * - 20만개 노드 -> 깊이는 20 내외
 * - K <= 1000000000000000000
 * - 각각 시뮬레이션으로는 절대 안됨
 * - 왼쪽 자식 노드로 떨어지는 경우
 *      - cur % 2 == 1 -> 왼쪽 자식
 *      - cur % 2 == 0 -> 오른쪽 자식
 * - 자식이 0개인 경우 -> 멈춤
 * - 자식이 1개인 경우 -> 무조건 해당 자식으로
 * - 자식이 2개인 경우
 *      - 왼쪽 자식 노드로 떨어지는 경우
 *          - cur % 2 == 1 -> 왼쪽 자식 cur/2+1
 *          - cur % 2 == 0 -> 오른쪽 자식  cur/2
 */