정렬⛓️- 위상정렬

▶ 유형

• 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다
• 정점 간 순서가 있다고 받아들이면 된다.
• 위상정렬이 성립하려면 유향그래프(indegree, outdegree)면서 사이클이 있으면 안된다. 

위상정렬은 각 정점의 진입차수를 세면서 진행한다. 

시작할 때 진입 차수가 0인 정점들을 스택에 넣고 정점을 꺼내면서 갈 수 있는 인접정점의 진입 차수를 1 감소시킨다.
그러다 인접정점의 진입 차수가 0이 되면 그 노드를 스택에 집어넣는다.

▶ 전략

순서대로 그려보자

진입 차수가 0인 1,3,4를 먼저 스택에 넣는다(큐여도 상관없을것같다)

진입 차수를 기준으로 자료구조에 넣어야하기 때문에 진입차수만 관리해줄 배열을 하나 선언해줘야한다.

그 다음 스택에서 빼면서 인접한 정점의 진입차수를 확인한다. -> 2, 7, 6이다(pop되면서 진입차수를 하나씩 감소시킨다)

정점 2의 진입차수가 0이됐으니까 push하고, pop하면서 인접한 정점의 진입차수를 하나씩 낮춘다.

6, 7이 진입차수 0되면서 push하고, pop한다 -> 5가 마지막에 남는다

보다보면 진입차수가 제일 작은것 부터 넣으면 되지않을까하는 생각이 든다. -> 우선순위 큐를 사용해보자...

꼭 우선순위큐가 아니어도 indegree배열로 처리하기때문에 상관없을 것 같다.

 

# 문제 풀어보기

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

1766번: 문제집

아주 위상정렬 그 자체인 문제다.

문제에서 우선 조건 중 정점 값이 작은 게 우선이라는 말이 있어서 minHeap으로 처리했다.

java

접기

import java.util.*;
import java.io.*;
 
class Main {
	static int n, m;
	static int[] indegree;
	static List<Integer>[] adj;
	static PriorityQueue<Integer> pq;
	static StringBuilder sb;
 
	static void topology() {
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0)
				pq.add(i);
		}
		while (!pq.isEmpty()) {
			int node = pq.poll();
			sb.append(node).append(" ");
			for (int nxt : adj[node]) {
				indegree[nxt]--;
				if (indegree[nxt] == 0)
					pq.add(nxt);
			}
		}
	}
 
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());// 문제의수 1~N까지
		m = Integer.parseInt(st.nextToken()); // 먼저 푸는 게 좋은 문제에 대한 개수
		adj = new ArrayList[n + 1]; // 부터 N까지의 인접리스트
		indegree = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			adj[i] = new ArrayList(); // N개의 정점 초기화
		}
		pq = new PriorityQueue<Integer>((o1, o2) -> {
			return o1 - o2;
		});
		sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			// to정점의 진입차수를 늘린다.
			adj[from].add(to);
			indegree[to]++;
		}
		// 진입차수가 0인애들만 pq에 넣고 시작하기
		topology();
		System.out.println(sb);
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^