[BOJ-2252][위상 정렬] 줄 세우기 - Java

문제 바로가기

2252번: 줄 세우기

 

위상 정렬을 사용해서 푸는 가장 기본적인 문제가 아닐까 싶습니다.

위상 정렬이란? ^^;;

 

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));
      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      
      List<Integer>[] students = new ArrayList[N+1];
      int[] inDegree = new int[N+1];
      
      for(int i = 0; i <= N; i++) students[i] = new ArrayList<>();
      
      for(int i = 0; i < M; i++) {
    	  st = new StringTokenizer(br.readLine(), " ");
    	  int a = Integer.parseInt(st.nextToken());
    	  int b = Integer.parseInt(st.nextToken());
    	  students[a].add(b);
    	  inDegree[b]++;
      }
      
      TopologicalSort(students, inDegree);
   }
   
   public static void TopologicalSort(List<Integer>[] graph, int[] inDegree) {
	   Queue<Integer> q = new LinkedList<>();
	   for(int i = 1; i < inDegree.length; i++) {
	   	  if(inDegree[i] == 0) q.offer(i);
	   }
	   
	   while(!q.isEmpty()) {
		   int cur = q.poll();
		   System.out.print(cur + " ");
		   for(int i = 0; i < graph[cur].size(); i++) {
			   int next = graph[cur].get(i);
			   if(--inDegree[next] == 0) q.offer(next);
		   }
	   }
	   /*
	    * 노드를 모두 방문하기 전에 q가 빈다면 싸이클이 존재하는 것이다.
	    */
   }
}

 

List<> 배열로 그래프를 만들어주고, 각 노드의 진입 차수를 저장한 inDegree[] 배열을 만들었습니다.

 

큐를 만들고, inDegree가 0인 노드들을 큐에 먼저 넣어줍니다.

큐에서 노드를 빼서 그 노드에서 가는 간선들을 삭제(inDegree--)하고, inDegree가 0이 되는 노드들을 계속해서 큐에 넣어주면 됩니다.

 

이 문제는 싸이클이 생기는 경우를 따로 체크하지 않아도 되기 때문에 간단히 풀 수 있답니다!!

 

 

위상 정렬 문제를 많이 풀어봐야겠습니다.

감사합니다 ^_^