백준 | 2252번. 줄세우기 - 위상 정렬 문풀

⬛ 백준 2252번. 줄세우기 - 위상 정렬 문풀

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

2252번: 줄 세우기

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

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

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

---

[위상 정렬]
- 사이클 없는 방향 그래프에서 노드 간 순서 결정하는 알고리즘
- 반드시 사이클이 없어야 명확하게 순서 결정 가능 (당연하다.)

위상 정렬의 전형적 문제들은 ‘답이 여러 가지인 경우 아무거나 출력하라’는 식으로 많이 나온다. 보통 진입차수 0 인 정점을 큐에 담아 출발점으로 두는데, 진입 차수 0인 정점이 여러 개인 경우 어떤 정점을 출발점으로 하느냐에 따라 답이 여러 개가 될 수도 있어서 그렇다.

시간복잡도 : O (V+E)
→ for문 돌며 차례대로 모든 노드 V를 확인하면서
      각 노드에서 나가는 간선들 하나씩 제거(E)하는 과정을 거치므로.

💚 문제 접근 방식

• 위상 정렬 문제의 경우 ‘답이 여러 개인 경우 아무거나 출력하라는’ 힌트가 있다. 비교 데이터를 기준으로 전체를 줄 세워 정렬시키라는 문제이므로, 전형적인 위상정렬 문제이다.
• 이 문제는 N명에 대한 키 비교 M번을 진행한 데이터를 가지고 전체 키 순서를 출력하라고 한다.

1. 진입차수 저장용 indegree[]를 선언한다.
2. M번의 비교횟수로 데이터를 그래프로 구성하는 동시에, 진입차수 값도 함께 갱신한다.
3. 데이터 저장 후 indegree[] == 0 인 점은 시작점이 될 수 있다. 얘네는 모두 Queue에 담는다.
4. while문 돌면서 Q가 빌 때까지, 현재 정점 뽑고, 현 정점에 이어진 다음 nx 정점에 대한 indegree[nx] 값을 1개 뺀다. 만약 뺀 뒤 0이 되면 큐에 담고 while문은 큐가 빌 때까지 반복한다.
5. 매번 차례대로 Q에서 뽑인 정점들이 ‘위상 정렬된 순서’ 이자 결과값이 된다.

💚 제출 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
 * 2252번. 줄 세우기 - 위상정렬 문풀
 * @author MYLG
 *
 */
public class Main {
	static int N, M;
	static int[] indegree;
	//실행 메인
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		List<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i = 0; i<=N; i++ ) graph.add(new ArrayList<>());
		
		indegree = new int[N+1];
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			//a -> b : 즉, a 먼저 스고, b 가 뒤에 슨다.
			graph.get(a).add(b);
			indegree[b]++;//진입차수++
		}
		
		/**
		 *	위상 정렬 시작 
		 */
		
		Queue<Integer> Q = new LinkedList<>();
		//진입차수 0 인 정점 모조리 담는다.
		for(int i=1; i<=N; i++) {
			if(indegree[i] == 0) Q.offer(i);
		}
		List<Integer> answer =new ArrayList<>();
		while(!Q.isEmpty()) {
			int cur = Q.poll();
			answer.add(cur);//하나씩 담고
			
			for(int nx : graph.get(cur)) {
				//현재 뽑은 애의 인접정점을 본다.
				indegree[nx]--;//하나 뺴주고
				if(indegree[nx] == 0) {
					Q.offer(nx);
				}
			}
		}
		//정답 출력
		for(int x : answer) System.out.print(x + " ");
	}
}