topological sort

위상정렬

연관 문제

백준.2056.작업

백준.2252.줄 세우기

설명

시간 복잡도 : O(V+E)

위상 정렬은 유향 비순환 그래프(Directed Acyclic Graph, DAG)에서 순서가 정해져있는 작업 차례로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다.

vector<vector<int> > graph;
vector<int> inDegree; // index 노드에서 갈 수 있는 노드의 개수
vector<int> result; // 정점을 방문하는 순서

// 진입 차수가 0인 노드를 큐에 삽입합니다
queue<int> q;
for (int node = 1; node <= N; node++) {
  if (inDegree[node] == 0) {
    q.push(node);
  }
}

// 정렬이 완전히 수행되려면 N개의 노드를 전부 방문합니다
for(int index = 0; index < N; index++) {
  if(q.empty()) {
    // n개를 방문하기 전에 큐가 비어버리면 사이클이 발생한 것
    // (이전에 진입차수가 0인 정점이 없었다는 의미이므로)
    break;
  }

  int cur = q.front();
  q.pop();
  result[index] = cur;

  for(int next : graph[cur]) {
    inDegree[next]--;

    // 새롭게 진입차수가 0이 된 정점을 큐에 삽입합니다
    if(inDegree[next] == 0) {
      q.push(next);
    }
  }
}

위상 정렬을 이용한 특정 정점까지 도달하는 최소 비용

위상 정렬을 수행하는 동안 각 index 까지 도달하는데 들어가는 cost를 갱신한다.

여기서 현재 작업과 연결되어 수행될 작업을 끝내기 위해 소요되는 시간은 최대 값이 되도록 해야한다.

'처음부터 현재 작업까지를 소요되는 시간 + 다음 작업 하나를 끝내는 데 필요한 시간' 값이 최대가 되어야 한다.

예시로 작업 A를 수행하기 위해 B와 C를 선행해야 하는 경우, B와 C중에 더 오래걸리는 작업을 수행해야 한다.

// costs : 해당 index까지 방문하는데 들어가는 최소 비용
// times 각 정점의 비용 (이전 정점에서 현재 정점까지 도달하는 데 비용)
vector<int> costs, times;
for (int node = 1; node <= N; node++) {
  costs[node] = times[node] = cost;
}

// 모든 노드를 방문하지 않아도 됨
while (!q.empty()) {
  int cur = q.front();
  q.pop();

  for (int next : graph[cur]) {
    times[next] = max(times[next], costs[next] + times[cur]);

    inDegree[next] -= 1;
    if (inDegree[next] == 0) {
      q.push(next);
    }
  }
}

for (int node = 1; node <= N; node++) {
  answer = max(answer, times[node]);
}