[C++/백준] 2252번: 줄 세우기*

문제 링크

2252번: 줄 세우기

 

풀이

위상 정렬 알고리즘을 알아야 풀 수 있는 문제.
모르겠어서 찾아봄 .. 알고리즘 자체는 간단하다. 사이클이 없는 방향 그래프에서 순서를 찾을 때 사용하는 듯하다.
해당 노드로 들어가는 간선이 없어야(다 해치워야) 그 노드를 방문할 수 있는 형태이다.

1. 입력을 받으며 인접 리스트를 만들고 진입 차수 벡터도 만들어준다.
2. 노드 1부터 n까지 확인하는데, 맨 첫번째 순서인 노드를 찾기 위해 진입차수가 0이고, 방문하지 않은 노드라면 위상 정렬을 실행한다.
3. queue에 첫 번째 노드를 넣고, 방문 처리 뒤 queue가 빌 때까지 반복한다.
   1. q에서 나온 노드를 출력하고, 해당 노드 cur과 연결된 노드들을 cur과의 간선을 끊었을 때(진입차수를 줄이고), 진입차수가 0이 된다면 q에 넣고 방문 처리한다.

 

코드

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1); // 인접 리스트
    vector<int> inDegree(n + 1, 0); // 진입차수
    vector<int> visited(n + 1); // 방문했는지
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        inDegree[b]++;
    }

    for (int i = 1; i <= n; i++)
    {
        // 진입차수가 0이고 방문하지 않은 노드라면 
        if (inDegree[i] == 0 && visited[i] == 0)
        {
            queue<int> q;
            q.push(i);
            visited[i] = 1;

            while (!q.empty())
            {
                int cur = q.front();
                cout << cur << ' ';
                q.pop();
                for (int j = 0; j < adj[cur].size(); j++)
                {
                    int next = adj[cur][j];
                    // 다음 노드에서 현재 노드와 연결된 간선을 끊는다.
                    inDegree[next]--; 
                    // 진입차수가 0이라면 q에 넣고 방문 처리
                    if (inDegree[next] == 0) 
                    {
                        q.push(next);
                        visited[next] = 1;
                    }
                }
            }
        }
    }

}