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

문제

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

1516번: 게임 개발

 

 

풀이

위상 정렬(Topology Sort) 알고리즘

위상 정렬(Topology Sort) 알고리즘

 

 

코드

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  vector<int> time(N + 1, 0);  // 건물을 짓는 데 걸리는 시간 저장 배열 크기 설정
  vector<int> indegree(N + 1, 0);  // 진입 차수 배열
  vector<vector<int>> outnode(N + 1);  // 건물의 개수만큼 인접 리스트 크기 설정
  for(int i = 1; i <= N; i++)
  {
    cin >> time[i];  // 해당 건물을 짓기 위한 시간

    while(true)
    {
      int pre;
      cin >> pre;
      if(pre == -1)
      {
        break;
      }

      indegree[i]++;  // 진입 차수 데이터 저장
      outnode[pre].push_back(i);  // 인접 리스트 데이터 저장
    }
  }

  queue<int> myqueue;  // 위상 정렬 수행
  vector<int> result(N + 1, 0);
  for(int i = 1; i <= N; i++)
  {
    // 진입 차수 배열의 값이 0인 건물(노드)을 큐에 삽입
    if(indegree[i] == 0)
    {
      myqueue.push(i);
    }
  }

  vector<bool> visited(N + 1, false);
  while(!myqueue.empty())
  {
    int now = myqueue.front();
    myqueue.pop();
    visited[now] = true;

    for(int next : outnode[now])
    {
      if(!visited[next])
      {
        indegree[next]--;
        result[next] = max(result[next], result[now] + time[now]);  // 결과 노드 업데이트

        if(indegree[next] == 0)
        {
          myqueue.push(next);  // 우선순위 큐에 타깃 노드 추가
        }
      }
    }
  }

  for(int i = 1; i <= N;i++)
  {
    result[i] += time[i];
    cout << result[i] << "\n";  // 위상 정렬 결과 출력
  }
  
  return 0;
}

 

 

오답

• 각 건물을 짓는 데 걸리는 최대 시간 업데이트

: max(현재 건물(노드)에 저장된 최대 시간, 이전 건물(노드)에 저장된 최대 시간 + 현재 건물(노드)의 생산 시간)

 

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

using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;
  vector<vector<int>> A;
  vector<int> indegree;  // 진입 차수 배열
  vector<int> selfBuild;
  A.resize(N + 1);
  indegree.resize(N + 1);
  selfBuild.resize(N + 1);
  
  for(int i = 1; i <= N; i++)
  {
    cin >> selfBuild[i];  // 해당 건물을 짓기 위한 시간
    // 인접 리스트 데이터 저장
    while(true)
    {
      int preTemp;
      cin >> preTemp;

      if(preTemp == -1)
      {
        break;
      }
      A[preTemp].push_back(i);
      indegree[i]++;  // 진입 차수 데이터 저장
    }
  }
  queue<int> queue; 
  // 위상 정렬 수행
  for(int i = 1; i <= N; i++)
  {
    if(indegree[i] == 0)
    {
      queue.push(i);
    }
  }
  vector<int> result;
  result.resize(N + 1);

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

    for(int next : A[now])
    {
      indegree[next]--;
      result[next] = max(result[next], result[now] + selfBuild[now]);
      if(indegree[next] == 0)
      {
        queue.push(next);
      }
    }
  }
  for(int i = 1; i <= N; i++)
  {
    cout << result[i] + selfBuild[i] << "\n";
  }
}