Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

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

4. 문제집

1766번

위상정렬 알고리즘을 변형하여 사전순으로 가장 앞선 위상정렬을 찾는 문제

이번 문제는 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 풀 문제의 순서를 결정해 주는 프로그램을 작성하는 문제이다.

순서가 정해져있는 작업을 차쳬로 수행할 때, 순서를 정해주는 문제로, 전형적인 위상 정렬 문제라고 할 수 있다. 먼저 풀어야 하는 문제와, 나중에 풀어야하는 문제를 분류하고 크기대로 정렬해주는 우선순위 큐를 사용해서 문제를 풀 수 있다.

Java / Python

• Java

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

public class Main {
	static int N, M;

	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());

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

		for (int i = 0; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());

			list[s].add(e);
			indegree[e]++;
		}

		bw.write(topologicalSort(indegree, list) + "\n");

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

	public static String topologicalSort(int[] indegree, ArrayList<Integer>[] list) {
		PriorityQueue<Integer> pque = new PriorityQueue<Integer>();
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < N + 1; i++) {
			if (indegree[i] == 0) {
				pque.offer(i);
			}
		}

		while (!pque.isEmpty()) {
			int node = pque.poll();
			for (int i : list[node]) {

				indegree[i]--;

				if (indegree[i] == 0)
					pque.offer(i);
			}
			sb.append(node + " ");
		}
		return sb.toString();
	}
}

• Python

import sys
import heapq
input = sys.stdin.readline

N,M = map(int,input().split())
arr = [[] for _ in range(N+1)]
indegree=[0 for _ in range(N+1)]
heap = []
result = []

for _ in range(M): 
    s, e = map(int,input().split())
    arr[s].append(e)
    indegree[e]+=1

for i in range(1,N+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

while heap:
    node = heapq.heappop(heap)
    result.append(node)
    for i in arr[node]:
        indegree[i]-=1 
        if indegree[i] == 0:
            heapq.heappush(heap, i)

for r in result:
    print(r , end=' ')