[BOJ] 14942 개미 🐜 - Java

1. 문제 링크

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

---

2. 문제 풀이

 이 문제에서는 방의 개수 최댓값이 100,000으로 주어집니다. 보통 input 값으로 10만 이상의 단위가 나오게 된다면 단순 구현으로는 못 푸는 경우가 많죠. 그래서 원래라면 희소 배열(Sparse Table)이라는 개념을 적용해서 풀어야 하는 문제이긴 합니다만. 이 문제는 단순 DFS로 풀립니다! 물론 아직 푼 사람이 그렇게 많은 편이 아닌 데다가 추가 테스트 케이스가 있어야 플래티넘다운 문제라고 할 수 있겠는데 .. 

 

근데 어쩔건데?

 

static void dfs(int node, int parentNode) {
        parent[node] = parentNode;
        for (Edge edge : graph.get(node))
            if (edge.to != parentNode) dfs(edge.to, node);
    }

 ... 저는 트리를 만들고선 부모를 찾아주는 형태로 만들어버렸습니다.

 

 "루트 노드가 1로 고정된 상태면 그냥 트리면 되는 거 아닌가? 게다가 이런 방식이면 부모로 거슬러 올라갈 수밖에 없으니 사이클이 존재할 수 없을 것이고, 무방향 그래프에서 굳이??"

 

라고 생각했지만 방 10만 개가 일렬로 구성된 트리라 칩시다. 그러면 10만 개의 방 하나하나를 1까지 올려 보내야 하는데 1에서 10만까지 더한 수의 총합은 자그마치  5,000,050,000  입니다. 대충 제한 시간 1초에 약 1억 정도의 연산을 수행할 수 있는데 상당한 숫자죠? 그래서 이 문제는 희소 배열을 활용해서 풀어야 하는 게 정론.

 

그래서 희소 배열이 대체 뭐냐고 묻는다면,

도서관

희소 배열은 도서관의 책장에서 실제로 책이 있는 칸만 기록하는 방식이라고 할 수 있겠습니다. 책장이 크더라도 비어 있는 칸을 모두 저장하지 않고, 책이 있는 위치와 정보만 기록하면 공간을 절약할 수 있겠죠? 그럼 이 문제에서는 부모와 부모의 부모 그리고 부모의 부모의 부모... 이런 식으로 부모의 부모의 부모의 부모의 부모의 부모까지 도달할 수 있는 에너지의 한계량을 미리미리 기록해서 구해버리면 연산 횟수를 줄일 수 있게 됩니다.

 

이와 관련해서 연습해 볼 만한 문제가 있습니다. 최소 공통 조상(LCA, Lowest Common Ancestor) 개념을 익히면서 희소 배열을 적용해 보는 것이죠. LCA는 트리 구조에서 두 노드가 공유하는 가장 가까운 조상을 찾는 개념입니다. 트리를 가족 관계라고 생각해 볼까요? 가장 가까운 공통 조상은 "같은 집안에서 가장 먼저 만나는 조상"입니다. 형제-자매의 공통 조상은 부모님. 사촌이라면 조부모님이 최소 공통 조상이 되겠죠.

 

       1
     /   \
    2     3
   / \   / \
  4   5 6   7
  //4와 7의 LCA : 1
  //4와 5의 LCA : 2

 

[LCA 관련]

11437 LCA

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

 

[LCA + 희소 배열 관련]

3176 도로 네트워크

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

11438 LCA2

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

13511 트리와 쿼리 2

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

 

음, LCA가 단독으로 적용되는 문제는 골드 수준이지만 LCA와 희소 배열이 융합된 문제들은 최소 플래티넘부터 시작이네요. 희소 배열까지 온 이상 조만간 세그먼트 트리도 학습해야겠죠. 희소 배열은 정적 데이터, 세그먼트 트리는 동적 데이터 환경에서 활용되는 차이가 있으니..

---

3. 소스 코드

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

public class Main {
    static int N;
    static int[] energy;
    static List<List<Edge>> graph = new ArrayList<>();
    static int[] parent;
    static int[] answer;

    static class Edge {
        int to, cost;

        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        energy = new int[N + 1];
        parent = new int[N + 1];
        answer = new int[N + 1];

        for (int i = 1; i <= N; i++) energy[i] = Integer.parseInt(br.readLine());

        for (int i = 0; i <= N; i++) graph.add(new ArrayList<>());

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Edge(b, cost));
            graph.get(b).add(new Edge(a, cost));
        }

        dfs(1, 0);

        for(int i = N; 0 < i; i--) answer[i] = process(i, energy[i]);

        for(int i = 1; i <= N; i++) System.out.println(answer[i]);
    }

    static void dfs(int node, int parentNode) {
        parent[node] = parentNode;
        for (Edge edge : graph.get(node))
            if (edge.to != parentNode) dfs(edge.to, node);
    }

    static int process(int node, int hp){
        int cur = node;
        while(cur != 1){
            int parentNode = parent[cur];
            int nextCost = 0;
            for(Edge edge : graph.get(cur)){
                if(edge.to == parentNode){
                    nextCost = edge.cost; break;
                }
            }
            if(hp < nextCost) return cur;
            hp -= nextCost;
            cur = parentNode;
        }
        return 1;
    }
}

---

4. 한줄평

難しいね...