[백준] 1005번 : ACM Craft

문제

 

---

풀이

 

위상정렬 문제다.

 

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

이 분께서 시간 복잡도까지 포함해서 잘 정리해 주셨다.

 

각 빌딩의 건설 시간을 저장할 벡터와 이 빌딩을 건설하기까지의 시간까지를 저장할 벡터를 각각 만들었다.

두번째 벡터를 갱신하는 과정에서 실수가 있었는데

처음엔 더이상 부모 정점이 없어 큐에 삽입이 가능한 시점에만 갱신을 했다.

 

그리고 '입력 예제 1'의 두번째 테스트케이스에서 19라는 결과가 나와서 그림을 그려보니 어디가 문제였는지 이해됐다.

건설에 걸리는 총 시간은 연결된 부모 건물이 하나씩 삭제될 때마다 갱신해야 한다.

 

이 실수를 잡아내고 나니 나머지는 수월했다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<int> indegree, time_cost, max_time;

int topology(int target) {
    queue<int> q;
    for (int i = 1; i < indegree.size(); i++) { //초기 큐 입력
        if (indegree[i] == 0) { //부모 정점이 없으면 큐에 삽입
            max_time[i] = time_cost[i];
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front(); //현재 빌딩
        int cost = max_time[cur]; //현재 빌딩을 건설하기까지 걸린 총 시간
        q.pop();

        if (cur == target) //목표 빌딩이라면 리턴
            return cost;
        for (int i = 0; i < graph[cur].size(); i++) {
            int connect = graph[cur][i]; //연결된 건물
            indegree[connect]--;
            max_time[connect] = max(max_time[connect], cost + time_cost[connect]); //건설에 걸리는 총 시간 갱신
            if (indegree[connect] == 0) //더이상 부모 정점이 없으면 큐에 삽입
                q.push(connect);
        }
    }
    return -1;
}

int main() {
    int T, N, K, X, Y, W;

    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> N >> K;
        graph.assign(N + 1, vector<int>(0)); //연결관계 그래프
        indegree.assign(N + 1, 0); //각 정점의 부모 정점 수
        time_cost.assign(N + 1, 0); //각 빌딩의 건설 시간
        max_time.assign(N + 1, 0); //각 빌딩을 건설하는데 걸리는 총 시간
        for (int i = 1; i <= N; i++)
            cin >> time_cost[i];
        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            graph[X].push_back(Y); //연결관계 삽입
            indegree[Y]++; //부모 정점의 수 증가
        }
        cin >> W; //목표 빌딩
        cout << topology(W) << '\n';
    }
}

전체 소스코드다.

 

        cin >> N >> K;
        graph.assign(N + 1, vector<int>(0)); //연결관계 그래프
        indegree.assign(N + 1, 0); //각 정점의 부모 정점 수
        time_cost.assign(N + 1, 0); //각 빌딩의 건설 시간
        max_time.assign(N + 1, 0); //각 빌딩을 건설하는데 걸리는 총 시간

먼저 각 테스트케이스마다 벡터들을 초기화 한다.

 

        for (int i = 1; i <= N; i++)
            cin >> time_cost[i];
        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            graph[X].push_back(Y); //연결관계 삽입
            indegree[Y]++; //부모 정점의 수 증가
        }

그리고 간단하게 입력을 받고

 

        cin >> W; //목표 빌딩
        cout << topology(W) << '\n';

목표 빌딩에 대한 위상정렬을 진행한다.

 

int topology(int target) {
    queue<int> q;
    for (int i = 1; i < indegree.size(); i++) { //초기 큐 입력
        if (indegree[i] == 0) { //부모 정점이 없으면 큐에 삽입
            max_time[i] = time_cost[i];
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front(); //현재 빌딩
        int cost = max_time[cur]; //현재 빌딩을 건설하기까지 걸린 총 시간
        q.pop();

        if (cur == target) //목표 빌딩이라면 리턴
            return cost;
        for (int i = 0; i < graph[cur].size(); i++) {
            int connect = graph[cur][i]; //연결된 건물
            indegree[connect]--;
            max_time[connect] = max(max_time[connect], cost + time_cost[connect]); //건설에 걸리는 총 시간 갱신
            if (indegree[connect] == 0) //더이상 부모 정점이 없으면 큐에 삽입
                q.push(connect);
        }
    }
    return -1;
}

큐로 구현한 위상 정렬이다.

 

    for (int i = 1; i < indegree.size(); i++) { //초기 큐 입력
        if (indegree[i] == 0) { //부모 정점이 없으면 큐에 삽입
            max_time[i] = time_cost[i];
            q.push(i);
        }
    }

먼저 초기 입력을 정해야 하는데 indegree 벡터를 살펴보면서 부모 정점이 없는, 그니까 indegree 값이 0인 빌딩들을 큐에 넣어준다. 해당 빌딩들을 건설하는 총 시간은 그냥 각 건물의 건설시간과 같다.

 

    while (!q.empty()) {
        int cur = q.front(); //현재 빌딩
        int cost = max_time[cur]; //현재 빌딩을 건설하기까지 걸린 총 시간
        q.pop();

        if (cur == target) //목표 빌딩이라면 리턴
            return cost;
        for (int i = 0; i < graph[cur].size(); i++) {
            int connect = graph[cur][i]; //연결된 건물
            indegree[connect]--;
            max_time[connect] = max(max_time[connect], cost + time_cost[connect]); //건설에 걸리는 총 시간 갱신
            if (indegree[connect] == 0) //더이상 부모 정점이 없으면 큐에 삽입
                q.push(connect);
        }
    }

이제 bfs 처럼 위상정렬을 진행한다.

 

        int cur = q.front(); //현재 빌딩
        int cost = max_time[cur]; //현재 빌딩을 건설하기까지 걸린 총 시간
        q.pop();

        if (cur == target) //목표 빌딩이라면 리턴
            return cost;

이번에 큐에서 빠져나온 빌딩이 우리가 목표로 했던 빌딩이라면 건설에 걸린 총 시간을 리턴한다.

 

        for (int i = 0; i < graph[cur].size(); i++) {
            int connect = graph[cur][i]; //연결된 건물
            indegree[connect]--;
            max_time[connect] = max(max_time[connect], cost + time_cost[connect]); //건설에 걸리는 총 시간 갱신
            if (indegree[connect] == 0) //더이상 부모 정점이 없으면 큐에 삽입
                q.push(connect);
        }

아니라면 해당 빌딩을 부모로 하는 모든 빌딩들의 indegree를 하나씩 줄여주고

그 자식 빌딩들의 건설 총시간을 갱신한다.

 

만약 그렇게 하고나서 자식 빌딩의 indegree가 0이 됐다면 이제 이 건물을 지을 수 있으니 큐에 넣어준다.