[백준/C++] 1516번 게임개발

1.문제 링크

게임개발

2. 풀이 전 계획과 생각

• 위상정렬 알고리즘

3. 풀이

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

vector<int> graph[501];
int indegree[501];
int time[501];
int totalTime[501];

void topology_sort(int n){
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(indegree[i]==0) {
        	q.push(i);
        	totalTime[i]=time[i];
		}
    }

    while(!q.empty()){
        int now = q.front();
        q.pop();

        for(int i=0;i<graph[now].size();i++){
            int next = graph[now][i];
			indegree[next]-=1;
            totalTime[next]=max(totalTime[next], totalTime[now]+time[next]);
            if(indegree[next]==0){
                q.push(next);
            }
        }
    }
}


int main(){
	int n;
	cin>>n;
	// 입력  
	for(int i=1;i<=n;i++){
		cin>>time[i];
		while(true){
			int temp;
			cin>>temp;
			if(temp==-1) break;
			graph[temp].push_back(i);
			indegree[i]+=1;
		}
	}
	
	// 위상정렬  
	topology_sort(n);
	
	// 답 출력 
	for(int i=1;i<=n;i++) cout<<totalTime[i]<<'\n';
}

각 건물이 완성되는데 걸리는 시간을 모두 출력해야 하기 때문에 이것을 저장하기 위해 totalTime 배열을 선언한다.

처음에 진입차수가 0인 건물을 큐에 push하고 그 건물의 totalTime을 그 건물을 짓는 시간으로 초기화 한다.

그리고 큐에서 원소를 한개씩 빼주면서 그 다음으로 가는 인접노드(그래프로 표현함)에 대해서 totalTime을 초기화한다. 이때 다음 건물을 짓는 시간에 현재까지 시간을 더한 값이 더 크다면 그 값으로 갱신해주는 작업을 한다. 그리고 그 건물의 진입차수를 1 뺀다. 만약 그 건물의 진입차수가 0이되면 q에 삽입한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감