[백준 2252번] 줄 세우기 (C++)

문제링크 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<int>inDegree, result;
vector<vector<int>>graph;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N, M;
    cin >> N >> M;
    result.resize(N+1);
    inDegree.resize(N+1);
    graph.resize(N+1);

    for(int i=0; i<M; i++)
    {
        int A, B;
        cin >> A >> B;
        graph[A].push_back(B);
        inDegree[B]++; //진입 차수 증가 (A가 우선)
    }

    queue<int>q;
    for(int i=1; i<=N; i++) //진입차수가 0인 정점들을 큐에 삽입
    {
        if(inDegree[i]==0) q.push(i);
    }

    for(int i=0; i<N; i++)
    {
        if(q.empty()) break; //큐가 비면 사이클 발생이므로 종료
        int cur = q.front(); //현재 방문 노드
        q.pop();
        result[i] = cur; //방문 노드 저장
        for(int j=0; j<graph[cur].size(); j++) //인접한 노드들의 진입 차수를 1씩 줄이고, 0이면 다시 큐에 삽입
        {
            int next = graph[cur][j];
            if(--inDegree[next]==0) q.push(next);
        }
    }

    for(int i=0; i<N; i++) cout << result[i] << " "; //방문 노드 출력

    return 0;
}

위상정렬의 입문급 문제이다.

이 문제를 통해서 위상정렬을 처음 접했기 때문에 따로 알아보고 풀었다.

 

먼저 그래프의 간선 정보를 입력받을 때 진입차수도 같이 입력 받는다.

위 문제의 경우 같이 입력받는 A, B에 대해 A가 B보다 앞에 있어야 하므로 B에 대해 진입 차수를 증가시켜준다.

그러고 나서 진입차수가 0인 정점들을 큐에 넣어준다.

 

큐에 담긴 원소를 하나씩 꺼내서 탐색을 시작하며, 이때 꺼낸 원소가 현재 방문 노드이다.

해당 방문 노드에 인접한 정점들과 연결되어있는 간선들을 제거해주기에 이때 인접한 정점들의 진입차수를 감소시킨다.

감소시킨 진입차수가 0이 된다면 또 큐에 넣어준다.

 

이를 모든 정점들에 대해 반복해서 실행하나 만약 모두 탐색하기 전에 큐가 비어있다면 사이클이 존재한다는 것이기에 종료시킨다.

제대로 탐색을 모두 마쳤다면 방문 순서가 정렬 순서이기에 방문 순서(cur)을 출력해주면 된다.