Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

1. 줄 세우기

2252번

위상정렬을 배우는 문제

이번 문제는 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하는 문제이다.

노드 갯수 N, 간선 갯수 M 을 받은 후, 간선의 가중치를 입력받고 위상 정렬한다.
위상정렬 (Topological Sort) :'사이클'이 없고 '방향'만 존재하는 그래프(DAG: Directed Acyclic Graph)에서 정점(Vertex)을 나열하는 방법
1. 정점과 연결된 다른 정점 리스트, 정점에 들어오는 그래프 개수 리스트 2개를 만든다.
2. 진입 루트(Indegree)가 없는 정점을 먼저 큐에 넣는다.
3. 해당 정점과 연결되어있는 노드에서 진입 루트 개수를 하나씩 빼준다.
4. 큐를 출력하고 제거한다. (큐가 빌 때까지 반복한다.)

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		LinkedList<Integer>[] list = new LinkedList[N + 1];
		int[] indegree = new int[N + 1];

		for (int i = 0; i < N + 1; i++) {
			list[i] = new LinkedList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list[x].add(y);
			indegree[y]++;
		}

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				queue.add(i);
			}
		}
		while (!queue.isEmpty()) {
			bw.write(queue.peek() + " ");
			int cur = queue.poll();

			for (int i = 0; i < list[cur].size(); i++) {
				int next = list[cur].get(i);
				indegree[next]--;
				if (indegree[next] == 0) {
					queue.add(next);
				}
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
inDegree = [0 for i in range(32001)]
graph = [[] for i in range(32001)]

queue = deque()
for i in range(M):
    x, y = map(int, input().split())
    arr.append([x, y])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

for i in range(1, N + 1):
    if inDegree[i] == 0:
        queue.append(i)
        
while queue:
    student = queue.popleft()
    print(student, end = ' ')
    for j in graph[student]:
        inDegree[j] -= 1
        if inDegree[j] == 0:
            queue.append(j)