백준 1005(ACM Craft)

문제

코드

성공 코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 위상정렬
 * 1. 방향 그래프
 * 2. 사이클 발생X(사이클 발생하면 모든 노드를 방문하지 않았는데 Queue가 빔)
 * -> 즉, 시작점이 없으면 답을 못구함
 * */
class Building{
    private int id;
    private int value;
    private int connectionCnt;
    private int totalValue;
    public Building(int id, int value){
        this.id = id;
        this.value = value;
        this.connectionCnt = 0;
        this.totalValue = 0;
    }
    public int getId() {
        return this.id;
    }
    public int getValue() {
        return this.value;
    }
    public int getConnectionCnt() {
        return this.connectionCnt;
    }

    public int getTotalValue() {
        return this.totalValue;
    }

    public void setTotalValue(int totalValue) {
        this.totalValue = totalValue;
    }

    public void addConnectionCnt() {
        this.connectionCnt++;
    }
    public void removeConnectionCnt() {
        this.connectionCnt--;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for(int t = 0; t < testCase; t++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());


            Building buildings[] = new Building[n + 1];
            StringTokenizer values = new StringTokenizer(br.readLine());
            for(int i = 1; i <= n; i++){
                buildings[i] = new Building(i, Integer.parseInt(values.nextToken()));
            }//Building Info

            List<ArrayList<Building>> list = new ArrayList<ArrayList<Building>>();
            for(int i = 0; i <= k+1; i++) {
                list.add(new ArrayList<>());
            }//list init

            for(int i = 0; i < k; i++){
                StringTokenizer relation = new StringTokenizer(br.readLine());
                int startIdx = Integer.parseInt(relation.nextToken());
                int endIdx = Integer.parseInt(relation.nextToken());

                list.get(startIdx).add(buildings[endIdx]);
                buildings[endIdx].addConnectionCnt();
            }//connect graph


            int lastBuildingIdx = Integer.parseInt(br.readLine());
            Building lastBuilding = buildings[lastBuildingIdx];
            Queue<Building> que = new LinkedList<>();
            for(int i = 1; i <= n; i++) {
                if(buildings[i].getConnectionCnt() == 0){
                    que.offer(buildings[i]);
                }
            }

            while (!que.isEmpty()){
                Building ing = que.poll();
                int id = ing.getId();
                if(id == lastBuildingIdx) break;
                for(int i = 0; i < list.get(id).size(); i++){
                    Building next = list.get(id).get(i);
                    next.setTotalValue(
                            Math.max(next.getTotalValue() , ing.getTotalValue() + ing.getValue())
                    );
                    next.removeConnectionCnt();
                    if(next.getConnectionCnt() == 0){
                        que.offer(next);
                    }
                }
            }

            System.out.println(lastBuilding.getTotalValue() + lastBuilding.getValue());
        }
    }
}