[ 백준 ] 1005 ACM Craft

Link | 백준 1005번 문제 : ACM Craft

📌 About

기본 개념은 다음과 같다.

각각의 건물들은 건설 시간과 사전 건설 건물 리스트를 가지고 있다.

건설 시간을 구하고자 하는 목표 건물부터 탐색을 시작한다.

탐색한 건물이 건설되지 않았다면 사전 건설 건물들의 리스트를 순환 탐색하며 탐색한다.

그 중에서 가장 시간이 길게 걸린 건물의 시간과 자신의 건설 시간을 더하여 건설을 완료한다.

만약 탐색한 건물이 건설이 완료되어 있다면 해당 건물의 시간을 반환한다.

📌 Solution

건설 시간을 측정하고자하는 건물의 번호를 G라고 할 때 시간 측정 방법은 다음과 같다.

Step 1. 해당 건물이 건설 완료되었는지 확인 (boolean built)

class Building {

    int time;
    boolean built = false;
    final List<Integer> preWorks = new ArrayList<>();
}

Step 2. 건설이 완료되지 않았으면 이전 사전 건설 목록들 중 최대 소요 시간 계산 (재귀)

public int getBuiltTime(List<Building> buildings) {
    if (!built) {
        int max = 0;
        for (Integer preWork : preWorks) {
            max = Math.max(max, buildings.get(preWork).getBuiltTime(buildings));
        }
        time += max;
        built = true;
    }
    return time;
}

📌 Code

GitHub Repository

class Building {

    int time;
    boolean built = false;
    final List<Integer> preWorks = new ArrayList<>();

    public Building(int time) {
        this.time = time;
    }

    public void addPreWork(int buildingNum) {
        preWorks.add(buildingNum);
    }

    public int getBuiltTime(List<Building> buildings) {
        if (!built) {
            int max = 0;
            for (Integer preWork : preWorks) {
                max = Math.max(max, buildings.get(preWork).getBuiltTime(buildings));
            }
            time += max;
            built = true;
        }
        return time;
    }
}

public void solve() throws IOException {
    StringTokenizer tokenizer;
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int buildingNum = Integer.parseInt(tokenizer.nextToken());
        int ruleNum = Integer.parseInt(tokenizer.nextToken());
        List<Building> buildings = Arrays.stream(("0 " + reader.readLine()).split(" "))
                .map(time -> new Building(Integer.parseInt(time))).collect(Collectors.toList());

        while (ruleNum-- > 0) {
            tokenizer = new StringTokenizer(reader.readLine());
            int pre = Integer.parseInt(tokenizer.nextToken());
            int post = Integer.parseInt(tokenizer.nextToken());
            buildings.get(post).addPreWork(pre);
        }

        result.append(buildings.get(Integer.parseInt(reader.readLine())).getBuiltTime(buildings))
        		.append("\n");
    }
}