[백준 / BOJ] C++ 2252 줄 세우기

2252번: 줄 세우기

 

문제

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

2252번: 줄 세우기

 

 

풀이

여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 사용하는 문제로 거저 주는 문제다. 각 순서를 입력받을 때마다 u -> v 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다.

 

indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례대로 front 원소에 대해 탐색한다. front 원소를 ans 배열에 추가하고 front에서 향하는 정점들에 대해 indegree 값을 1 감소시키고 0이 되면 큐에 push 해 준다. 위 과정이 끝난 뒤 ans 배열의 값을 모두 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  vector<int> edge[32001], inDegree(32001, 0), ans;
  cin >> N >> M;
  while (M--) {
    int u, v;
    cin >> u >> v;
    inDegree[v]++;
    edge[u].push_back(v);
  }
  queue<int> q;
  for (int i = 1; i <= N; i++)
    if (inDegree[i] == 0)
      q.push(i);
  for (int i = 1; i <= N; i++) {
    int node = q.front();
    q.pop();
    ans.push_back(node);
    for (int next : edge[node])
      if (--inDegree[next] == 0)
        q.push(next);
  }
  for (int e : ans)
    cout << e << ' ';
  return 0;
}