[Algorithm][위상 정렬] 백준 2252 - 줄 세우기

알고리즘 분류

 위상 정렬

 

시간 복잡도

 \( O(V + E) \)

 

문제 링크

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

---

 

 선행되어야 할 인덱스들이 주어지면서 가능한 순서를 답으로 제출하는 위상 정렬의 문제입니다. 입력으로써 특정 인덱스 2개가 주어지면 첫 번째 숫자와 두 번째 숫자는 꼭 지켜야 할 순서입니다.

 

 테스트 케이스 2번을 예시로 든다면 아래 그림처럼 4가 2를 가리키고 3이 1을 기리 키는 구조가 됩니다. 이 두 관계를 제외하고는 각 숫자들은 서로 연관되지 않습니다.

 위상 정렬의 핵심은 "간선이 없는 노드를 처리하자" 입니다. 여기서 간선이 없는 노드의 뜻은 "가리킴을 당하지 않는 노드"입니다. 그래서 저의 풀이는 Queue를 사용했고 처리하는 과정에서 간선이 없는 노드가 생겨난다면 다시 Queue에 넣는 작업을 진행합니다. 이때 Queue에서 나오는 순서가 이 문제의 답입니다. 위의 예제에서는 현재 4와 3이 간선이 없는 노드입니다( 가리킴을 당하지 않는 노드 ). 그래서 Queue에 4와 3이 가장 먼저 들어갑니다. Queue에서 4가 나오면서 가리키고 있던 노드를 순회하고, 대상 노드의 간선 수를 -1 시킵니다. 즉 4가 가리키고 있던 2 노드의 간선 수는 기존 1에서 0이 되어 Queue에 추가됩니다. 이렇게 Queue가 비워질 때까지 반복하면서 최종 결과를 출력합니다.

 

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int indegree[] = new int[n+1];
        Vector<Integer> v[] = new Vector[n+1];

        for(int i=0; i<n+1; i++)
            v[i] = new Vector<Integer>();

        for(int i=0, A,B; i<m; i++){
            A = sc.nextInt();
            B = sc.nextInt();
            v[A].add(B);
            indegree[B]++;
        }

        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=1; i<n+1; i++)
            if(indegree[i]==0) q.add(i);
            
        for(int i=0; i<n; i++){
            int cur = q.poll();

            System.out.println(cur);
            for(int j=0; j<v[cur].size(); j++)
                if(--indegree[v[cur].get(j)]==0) q.add(v[cur].get(j));
        }
    }
}

 

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define FOR(x,n,m) for(int x=n; x<(m); x++)

int n,m;

int indegree[32000];
vector<int> adj[32000];
int result[32000];

int main()
{
    cin >> n >> m;
    
    FOR(i,0,m){
        int a,b; cin >> a >> b;
        adj[a-1].push_back(b-1);
        indegree[b-1]++;
    }
    
    queue<int> q;
    FOR(i,0,n) if(indegree[i] == 0) q.push(i);
    
    FOR(i,0,n){
        int cur = q.front(); q.pop();
        
        cout << cur+1 << " ";
        for(auto e : adj[cur])
            if(--indegree[e] == 0) q.push(e);
    }
    
    return 0;
}