[C/C++] 백준 #1005 ACM Craft(위상 정렬)

그래프 이론과 관련된 알고리즘은 종류도 여러가지이고, 하나의 문제에 해법도 여러가지가 존재합니다.

 

프림, 다익스트라, A* 로 이루어지는 알고리즘은 같은 형태이지만, 인접 노드들을 찾아서 업데이트하는 것만 다른 알고리즘이죠.

플로이드 워샬, 크르스칼 등등 사실 다 기억하고 다닐 수도 없습니다.  이번 위상정렬 알고리즘은 간단해서 그나마 외우고 다닐만한 알고리즘이라고 생각됩니다.

 

위상정렬

문제 자체는 스타크래프트와 같은 전략시뮬레이션 게임의 테크트리와 비슷합니다.  내용이야 그렇지만, 결국 위상정렬을 통하여 최종 테크트리가 이루어지는 최단 시간을 찾는 문제입니다.

 

문제는 아래와 같습니다.

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

 

위상정렬도 그래프이다보니, 인접 노드들을 인접행렬을 쓸 것인지, 아니면 인접리스트를 쓸 것인지 결정해야 합니다.

한동안 링크드 리스트를 이용한 인접리스트를 써왔는데, 귀찮기 그지 없네요.  요즘은 그냥 vector 자료구조를 이용합니다.

 

위상정렬의 핵심은 입력간선이 없는 노드들을 선택하여 출력간선들을 없애는 과정입니다.  그래프가 싸이클을 이루지 않는 이상 결국 연결된 모든 노드들에 대해서 방문을 할 수 있습니다.

 

아래는 제가 만든 소스입니다.  소스는 참고용으로만 보세요.

//------------------------------------------------------------------------------
//  baekjoon #1005 - ACM Craft
//    - by Aubrey Choi
//    - created at 2019-05-31
//------------------------------------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <vector>

int main()
{
  int t, d[1000], node[1000], c[1000], n, k, w, from, to, i;
  char adj[1000][1000];
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d%d", &n, &k);
    std::queue<int> q;
    std::vector<int> adj[n];
    memset(node, 0, n*sizeof(int));
    memset(c,0,n*sizeof(int));
    for(i=0;i<n;i++) scanf("%d",d+i);
    while(k--)
    {
      scanf("%d%d", &from, &to); from--,to--;
      adj[from].push_back(to);
      c[to]++;
    }
    for(i=0;i<n;i++) if(!c[i]) q.push(i);
    scanf("%d", &w); w--;
    for(;;)
    {
      int s=q.front(); q.pop();
      if(s==w) break;
      for(auto j:adj[s])
      {
        int v = node[s] + d[s];
        if(v > node[j]) node[j] = v;
        if(!(--c[j])) q.push(j);
      }
    }
    printf("%d\n", node[w]+d[w]);
  }
  return 0;
}