BOJ-백준 1516번 게임 개발 C++

BOJ-백준 1516번 게임 개발 C++ 문제 풀이 입니다.

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

1516번: 게임 개발

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

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

#define MAX 501

using namespace std;

int n, inDegree[MAX], ttime[MAX], result[MAX];
vector<int> a[MAX];

void topology(){
  queue<int> q;
  for(int i=1; i<=n; i++){
    if(inDegree[i]==0) {
      result[i] = ttime[i];
      q.push(i);
    }
  }
  for(int i=1; i<=n; i++){
    if(q.empty()){
      return;
    }
    int x= q.front();
    q.pop();
    for(int i=0; i< a[x].size(); i++){
      int y= a[x][i];
      if(--inDegree[y]==0){
        q.push(y);
        }
        result[y] = max(result[y], result[x]+ttime[y]);
    }
  }
  for(int i=1; i<=n; i++){
    printf("%d\n",result[i]);
  }
}

int main() {
  cin>> n;
  for(int i=1; i<=n; i++){
    scanf("%d", &ttime[i]);
    while(1){
      int x;
      scanf("%d", &x);
      if(x==-1) break;
      inDegree[i]++;
      a[x].push_back(i);
  }
  }
  topology();
}

 

📌 해설

위상 정렬 문제입니다. 게임 건물을 짓는데에 시간이 들고, 해당 건물을 짓기 전 먼저 지어야 하는 건물이 있을 수 있으며(조건), 여러 개의 건물을 동시에 지을 수 있습니다. 1부터 N까지 모든 건물을 짓는데 걸리는 최소 시간을 출력해야 하는 문제입니다. 

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 501

using namespace std;

int n, inDegree[MAX], ttime[MAX], result[MAX];
vector<int> a[MAX];

1. 필요한 변수를 모두 선언합니다. 

건물의 종류 N이 최대 500까지 입력될 수 있으므로 MAX를 501로 정의합니다. 

inDegree는 진입차수, ttime은 각 건물 짓기에 소요되는 시간, result는 최종 출력 결과로 선언합니다. 

a는 건물이 지어지는 순서의 정보를 담습니다. 

 

int main() {
  cin>> n;
  for(int i=1; i<=n; i++){
    scanf("%d", &ttime[i]);
    while(1){
      int x;
      scanf("%d", &x);
      if(x==-1) break;
      inDegree[i]++;
      a[x].push_back(i);
  }
  }
  topology();
}

2. 필요한 입력을 받고 위상정렬 함수(topology())를 호출합니다. 

 

void topology(){
  queue<int> q;
  for(int i=1; i<=n; i++){
    if(inDegree[i]==0) {
      result[i] = ttime[i];
      q.push(i);
    }
  }
  for(int i=1; i<=n; i++){
    if(q.empty()){
      return;
    }
    int x= q.front();
    q.pop();
    for(int i=0; i< a[x].size(); i++){
      int y= a[x][i];
      if(--inDegree[y]==0){
        q.push(y);
        }
        result[y] = max(result[y], result[x]+ttime[y]);
    }
  }
  for(int i=1; i<=n; i++){
    printf("%d\n",result[i]);
  }
}

3. 큐를 하나 선언하고, 진입차수가 0인 건물(정점)에 대해 건물짓기에 소요되는 시간을 result에 초기화 하고 큐에 해당 건물(정점)을 삽입합니다. 

3-1. 모든 정점을 돌도록 for문을 장성합니다.

3-2. 큐가 비어있다면 위상정렬을 종료합니다(사이클 발생하는 경우)

3-3. 큐에서 원소를 하나 빼서 x에 저장합니다. 

3-4. 건물 x(정점)에 연결된 건물들을 모두 탐색하는 for 문을 작성합니다. 

    3-4.(1) x가 지어져야 지을 수 있는 건물의 정점을 y에 저장하고 진입차수를 하나 뺍니다. 

    3-4.(2) 진입차수를 하나 뺐을때 0이 된다면 큐에 y를 삽입합니다. 

    3-4(3) result[y] 는 y 건물을 지을때 걸리는 최소 시간을 의미합니다. x를 짓는데 걸린 시간과 y를 짓는데 걸린 시간을 합한것과, result[y]를 비교하여 더 큰 값을 result[y]에 저장합니다.

y를 지을때 지어야 하는 건물이 여러개일 때, 건물은 동시에 지어질 수 있으므로 더 오래 걸리는 건물의 시간을 기록할 수 있습니다. 

3-5. 위 과정을 반복하고 모든 반복문이 종료되면 결과를 출력합니다. 

 

 

 

::

 

위상정렬을 활용하여 임계경로를 구할 수 있는 문제였습니다. 

어렵다...!