1005번 - ACM Craft(비순환 그래프)

문제:

 

풀이:

이 문제에서는 건물 W를 건설하는데 필요한 최소시간이라고 하지만, 최대 시간이라고 생각하는게 편하다.

위의 그림에서, 4번 건물을 건설하는데 까지 걸리는 시간은 120초이다.

10 + 1 + 10초를 선택해야 하는 것이 아닌, 10 + 100 + 10초를 선택해야 하기 때문에 최대 시간이라고 생각해야 한다.

 

위 그림은 너무 단편적이기 때문에 하나의 예시를 더 들어보겠다.

원 안의 큰 숫자는 각 건물의 인덱스를 나타내고, 초록 숫자는 각 건물을 짓는데 필요한 시간을 나타낸다.

예시에서 W는 7이다.

1. 1번 노드는 시작 노드이며, 3, 2번 노드로 갈 수 있다.
2. 2번 노드의 다음 노드는 4, 5번 노드이다,
   1. 4번 노드까지 걸리는 시간은 10 + 20 + 5이다.
   2. 5번 노드까지 걸리는 시간은 10 + 20 + 8이다.
      5번 노드의 다음 노드는 아직 탐색 할 수 없다.
3. 3번 노드의 다음 노드는 6번 노드, 5번 노드이다.
   1. 6번 노드까지 걸리는 시간은 10 + 1 + 7 이다.
   2. 3번 노드를 통해 5번 노드까지 도착하는 시간은 10 + 1 + 8이다.
      2번 노드를 통해 5번 노드까지 걸리는 시간은 10 + 20 + 8로, 2번 노드를 통해 이동하는  시간이 더 길다.
      고로 1 -> 2 -> 5 경로를 선택해야 한다.
      5번 노드의 이전 노드를 모두 탐색 했으므로, 5번 노드를 탐색할 수 있다.
4. 5번 노드의 다음 노드는 7번 노드이다.
   1 -> 2 -> 5 -> 7을 선택할 경우 걸리는 시간은 10 + 20 + 8 + 1이다.
   아직 7번 노드의 이전 노드를 모두 탐색하지 않았으므로, 7번 노드는 아직 탐색할 수 없다.
5. 6번 노드의 다음 노드는 7번 노드이다.
   1 -> 3 -> 6 -> 7 경로를 선택할 경우 걸리는 시간은 10 + 1 + 7 + 1이다.
   7번 노드에 도착하는 두 경로중 더 시간이 오래 걸리는 경우는 1 -> 2 -> 5 -> 7 경로로, 걸리는 시간은 39이다.
6. 7번 노드에 도착하면, 이후 노드는 탐색할 필요는 없다.

위 풀이 과정에서 문제를 푸는데 중요한 조건은 아래와 같다.

• 어떤 노드의 다음 노드를 탐색하기 위해서는, 다음 노드에 대한 정보가 있어야 한다.
• 어떤 노드를 탐색하기 위해서는, 해당 노드의 이전 노드의 탐색이 모두 끝났어야 한다.
• 만일 어떤 노드까지 도달하는데, 두 경로 이상의 경우의 수가 있다면, 두 경로중 더 오래걸리는 경로를 선택해야 한다.
• 노드 W에 도착하면 이후 노드는 탐색할 필요가 없다.

위 조건을 활용하여 Building 클래스를 작성해보자.

class Building {
    private int buildingId;
    private int buildTime;
    private List<Building> nextBuildings;
    private int totalTime;
    private int prevCount;

    Building(int buildingId, int buildTime) {
        this.buildingId = buildingId;
        this.buildTime = buildTime;
        this.nextBuildings = new ArrayList<>();
        this.totalTime = buildTime;
        this.prevCount = 0;
    }

}

• 빌딩의 인덱스(ID) - buildingId
• 해당 빌딩을 건설하는데 걸리는 시간 - buildTime
• 다음 건설 해야하는 빌딩의 정보 - nextBuildings
• 지금까지 빌딩을 건설하는데 들은 시간 - totalTime
• 탐색되지 않은 이전 빌딩의 개수  - prevCount

위와 같은 클래스 변수가 필요할 것이다.

생성자 생성시, totalTime을 buildTime으로 초기화 해줘야 한다.

 

이제 클래스 메서드를 작성해보자.

아래는 다음 빌딩을 저장하고, 다음 빌딩의 prevCount를 1 증가시켜주는 메서드이다.

void addNextBuilding(Building nextBuilding) {
    this.nextBuildings.add(nextBuilding);
    nextBuilding.prevCount += 1;
}

prevCount가 0이라는 소리는 이전의 빌딩이 모두 탐색되었다는 소리이다.

즉 prevCount를 1씩 줄여주는 메서드도 필요하다.

void subPrevCount() {
    this.prevCount -= 1;
}

 

아래는

"만일 어떤 노드까지 도달하는데, 두 경로 이상의 경우의 수가 있다면, 두 경로중 더 오래걸리는 경로를 선택해야 한다."

라는 조건을 만족시키는 메서드이다.

void updateTotalTime(Building prevBuilding) { // 건설 시간을 구하기 위해선, 이전 노드의 총 건설 시간중 가장 긴 경우를 택해야 함
    this.totalTime = Math.max(this.totalTime, this.buildTime + prevBuilding.totalTime);
}

아래는 getter 메서드들이다.

int getBuildingId() {
    return buildingId;
}

List<Building> getNextBuildings() {
    return nextBuildings;
}

int getTotalTime() {
    return totalTime;
}

int getPrevCount() {
    return prevCount;
}

 

입력은 아래와 같은 방식으로 받을 것이다.

for (int j = 0; j < K; j++) { // 각 입력 처리
    st = new StringTokenizer(br.readLine());
    int X = Integer.parseInt(st.nextToken());
    int Y = Integer.parseInt(st.nextToken());

    Building building = buildingList.get(X);
    Building nextBuilding = buildingList.get(Y);
    building.addNextBuilding(nextBuilding);
}

다음 빌딩 정보를 저장하는 동시에, 다음 빌딩의 prevCount를 1 증가시킨다.

 

위 클래스, 메서드를 이용해서 W번째 빌딩의 건설 시간을 구하는 메서드를 작성해보자.

static int totalBuildTime(int W, List<Building> buildingList) { // W번째 빌딩의 건설 시간을 구함
    Queue<Building> queue = new LinkedList<>();
    for (Building building : buildingList) { // 처음 빌딩부터 시작
        if (building.getPrevCount() == 0) {
            queue.add(building);
        }
    }

    while (!queue.isEmpty()) {
        Building building = queue.poll();
        if (building.getBuildingId() == W) { // 건물 W의 건설 시간을 이미 알고 있음
            break;
        }

        for (Building nextBuilding : building.getNextBuildings()) { // 다음 빌딩의 건설 시간을 구하기 위한 과정
            nextBuilding.subPrevCount();
            nextBuilding.updateTotalTime(building);
            if (nextBuilding.getPrevCount() == 0) {
                queue.add(nextBuilding);
            }
        }
    }

    return buildingList.get(W).getTotalTime();
}

1. prevCount가 0이면 시작노드이므로, 시작노드를 찾아 queue에 저장해놓는다.
2. queue에 데이터가 있는 동안 아래 반복문을 실행한다.
   1. queue에서 빌딩 객체 하나를 꺼낸다.
   2. 해당 빌딩의 Id가 W라면 반복문을 종료한다.(이후의 빌딩은 고려할 필요 없음)
   3. 빌딩 객체의 nextBuildings에 저장되어 있는 다음 빌딩들에 대해 반복문을 실행한다.
      1. 다음 빌딩의 prevCount에서 1을 빼준다.(지금 빌딩을 탐색하므로)
      2. 지금 빌딩을 지나는 경로의 시간을 계산해, 다음 빌딩의 totalTime를 update한다.
      3. 만일 다음 빌딩의 prevCount가 0이라면(이전 빌딩을 모두 탐색함)
         queue에 다음 빌딩을 추가한다.
3. w번째 빌딩을 건설하는데 걸리는 총 시간을 반환한다.

 

전체코드:

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

class Building {
    private int buildingId;
    private int buildTime;
    private List<Building> nextBuildings;
    private int totalTime;
    private int prevCount;

    Building(int buildingId, int buildTime) {
        this.buildingId = buildingId;
        this.buildTime = buildTime;
        this.nextBuildings = new ArrayList<>();
        this.totalTime = buildTime;
        this.prevCount = 0;
    }

    int getBuildingId() {
        return buildingId;
    }

    List<Building> getNextBuildings() {
        return nextBuildings;
    }

    int getTotalTime() {
        return totalTime;
    }

    int getPrevCount() {
        return prevCount;
    }

    void addNextBuilding(Building nextBuilding) {
        this.nextBuildings.add(nextBuilding);
        nextBuilding.prevCount += 1;
    }

    void subPrevCount() {
        this.prevCount -= 1;
    }

    void updateTotalTime(Building prevBuilding) { // 건설 시간을 구하기 위해선, 이전 노드의 총 건설 시간중 가장 긴 경우를 택해야 함
        this.totalTime = Math.max(this.totalTime, this.buildTime + prevBuilding.totalTime);
    }
}

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

        int T = Integer.parseInt(br.readLine());

        Queue<Integer> answer = new LinkedList<>();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 수
            int K = Integer.parseInt(st.nextToken()); // 규칙 수

            List<Building> buildingList = new ArrayList<>();
            buildingList.add(new Building(0,0));
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) { // 각 빌딩 객체 생성
                buildingList.add(new Building(j, Integer.parseInt(st.nextToken())));
            }

            for (int j = 0; j < K; j++) { // 각 입력 처리
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());

                Building building = buildingList.get(X);
                Building nextBuilding = buildingList.get(Y);
                building.addNextBuilding(nextBuilding);
            }

            int W = Integer.parseInt(br.readLine());
            answer.add(totalBuildTime(W, buildingList));
        }

        while (!answer.isEmpty()) { // 정답 출력
            System.out.println(answer.poll());
        }
    }

    static int totalBuildTime(int W, List<Building> buildingList) { // W번째 빌딩의 건설 시간을 구함
        Queue<Building> queue = new LinkedList<>();
        for (Building building : buildingList) { // 처음 빌딩부터 시작
            if (building.getPrevCount() == 0) {
                queue.add(building);
            }
        }

        while (!queue.isEmpty()) {
            Building building = queue.poll();
            if (building.getBuildingId() == W) { // 건물 W의 건설 시간을 이미 알고 있음
                break;
            }

            for (Building nextBuilding : building.getNextBuildings()) { // 다음 빌딩의 건설 시간을 구하기 위한 과정
                nextBuilding.subPrevCount();
                nextBuilding.updateTotalTime(building);
                if (nextBuilding.getPrevCount() == 0) {
                    queue.add(nextBuilding);
                }
            }
        }

        return buildingList.get(W).getTotalTime();
    }
}

 

시행착오:

클래스를 이용해서 문제를 푸는것이 처음에는 복잡하게 느껴졌지만,
이제는 오히려 편하게 느껴지고, 코드 가독성이 높아진 것을 느끼고 있다.

각자의 책임을 확실하게 하며 점점 객체지향적 프로그래밍에 익숙해지고 있는 듯 하다.