PowerOutage

Code

import java.util.LinkedList;

import java.util.Queue;

public class PowerOutage

{

    public int estimateTimeout(int[] fromJunction, int[] toJunction, int[] ductLength) {

        int n = fromJunction.length;

        int sum = 0;

        int len = 0;

        int[] dlSum = new int[50];

        for (int i = 0; i < n; i++)

            sum += ductLength[i];

        Queue<Integer> q = new LinkedList<Integer>();

        q.add(0);

        while (q.size() != 0) {

            int jn = q.poll();

            for (int i = 0; i < n; i++) {

                if (fromJunction[i] == jn) {

                    q.add(toJunction[i]);

                    dlSum[toJunction[i]] += dlSum[jn] + ductLength[i];

                    if (dlSum[toJunction[i]] > len) len = dlSum[toJunction[i]];

                }

            }

        }

        return 2*sum - len;

    }

}

Problem

아파트의 전력 공급이 중단 되는 문제가 발생하여 아파트 지하에 있는 변압기를 점검하고 필요시 고쳐야 한다. 모든 변압기를 방문하는데 걸리는 최단 시간은 얼마인가?

Explanation

나무(tree) 자료구조를 사용하는 문제로 입력값을 나무로 그려서 표현하면 이해하기 쉽다. 모든 변압기를 방문해야 하고 막다른 길에 도달하면 부모(parent) 또는 근(root)으로 올라간다. 가장 오랜 시간이 걸리는 경로를 제일 마지막에 방문하면 다시 돌아오지 않아도 되므로 시간을 절약할 수 있다. 따라서 모든 소요 시간은 2*sum - len이다. 2*sum은 각 경로를 두 번 왔다갔다한 시간이고 len은 가장 오래 걸리는 경로의 시간이다 (한 번만 방문하므로 2*sum에서 빼줘야 한다).

References

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm144