[백준/BOJ] 1516번: 게임 개발 ( 위상 정렬 사용법 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1516

 

풀이

이 문제는 건물 건설에 걸리는 시간을 출력하는 문제입니다.

그런데, 이 건설 시간은 한 건물을 건설하는데 사전에 필요한 건물들의 건설 시간을 모두 포함한 시간입니다.

 

이러한 문제를 푸는 데, 위상 정렬( topology sort ) 알고리즘이 적합합니다.

위상 정렬은 어떤 과제를 해결하는데 먼저 수행해야 되는 작업을 나열하는 알고리즘입니다.

 

위상 정렬에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 위상 정렬( Topology Sort )

 

위상 정렬을 사용하기 위해선, 먼저 그래프를 구성해야 합니다.

#define SIZE    500

int indegree[SIZE+1];	
int ctime[SIZE+1];	// 건물을 건설하는데 필요한 시간
int prevtime[SIZE+1];	// 사전 건물들을 건설하는데 필요한 시간
vector<int> graph[SIZE+1];	

for( int i = 1; i <= N; i++){
    ctime[i] = readInt();

    while(true){
        int v = readInt();	// 사전 건물의 번호
        if ( v == -1)
            break;

        graph[v].push_back(i);
        indegree[i]++;
    }
}

사전 건물이 있는 경우, 이 건물 v에서 i번째 건물로 이어지는 간선이 있다고 볼 수 있습니다.

따라서, i번째 건물의 indegree를 늘려줍니다.

여기서, 정점의 indegree는 다른 정점에서 출발하여, 그 정점에 이어지는 간선의 개수를 말합니다.

 

그래프가 구성되면, 이제 위상 정렬을 적용합니다.

void Topology_Sort(int N){

    queue<int> q;

    for( int i = 1; i <= N; i++){
        if ( indegree[i] == 0)  // 정렬을 시작할 정점
            q.push(i);
    }
    
    while( !q.empty()){
        int vert = q.front();
        q.pop();

        for( int x : graph[vert]){
            indegree[x]--;
            
            // 사전 건물의 건설시간
            prevtime[x] = max( prevtime[x], prevtime[vert] + ctime[vert] );    

            if ( indegree[x] == 0){
                q.push(x);
            }
        }
    }
}

한 건물의 사전 건설시간은, 이전에 건설해야 하는 여러 건물들의 건설 시간 중에서 가장 오래 걸리는 시간이 됩니다.

예를 들어, 사건 건물 A의 건설 시간이 10, B가 15, C는 20의 건설 시간을 갖는다면, A, B, C의 총 사전 건설 시간은 20입니다. ( 건물들은 동시에 건설이 가능합니다. )

 

그리고, 건물의 건설시간은 사전 건설시간 + 본 건물 건설 시간이 됩니다.

for( int i = 1; i <= N; i++){
    printf("%d\n", prevtime[i] + ctime[i]);	// 각 건물 건설 시간
}

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
int ridx, nidx;

inline char read() {
    if (ridx == nidx) {
        nidx = fread(rbuf, 1, 1 << 20, stdin);
        if (!nidx) return 0;
        ridx = 0;
    }
    return rbuf[ridx++];
}
inline int readInt() {
    int sum = 0;
    char now = read();
    bool flg = false;

    while (now <= 32) now = read();
    if (now == '-') flg = true, now = read();
    while (now >= 48) sum = sum * 10 + now - '0', now = read();

    return flg ? -sum : sum;
}
//----------------------------------------------------------

#define SIZE    500

int indegree[SIZE+1];
int ctime[SIZE+1];
int prevtime[SIZE+1];
vector<int> graph[SIZE+1];

void Topology_Sort(int N){

    queue<int> q;

    for( int i = 1; i <= N; i++){
        if ( indegree[i] == 0)  // 정렬을 시작할 정점
            q.push(i);
    }
    
    while( !q.empty()){
        int vert = q.front();
        q.pop();

        for( int x : graph[vert]){
            indegree[x]--;
            
            // 사전 건물의 건설시간
            prevtime[x] = max( prevtime[x], prevtime[vert] + ctime[vert] );    

            if ( indegree[x] == 0){
                q.push(x);
            }
        }
    }
}

int main(){

    int N = readInt();

    for( int i = 1; i <= N; i++){
        ctime[i] = readInt();

        while(true){
            int v = readInt();
            if ( v == -1)
                break;

            graph[v].push_back(i);
            indegree[i]++;
        }
    }   

    Topology_Sort(N);

    for( int i = 1; i <= N; i++){
        printf("%d\n", prevtime[i] + ctime[i]);
    }

    return 0;
}