<Algorithm> 46. 2252번 줄세우기

1. 2252번 줄세우기

• 기본 위상정렬 문제, 위상정렬은 우선순위에 맞게 정렬하는 것을 의미한다.

• BFS로만 접근 했을 때 1 -> 3, 2 -> 3 을 할경우 1 - > 3 - > 2 가 출력되는 문제가 있었다. 이는 우선순위를 고려하지 않은 오류이다.

• 예를 들어 게임 상에서 1번 퀘스트와 2번퀘스트를 완료해야 3번 퀘스트를 할 수 있는 때 이 순서를 묻는 문제와 같다.

• 먼저 해야하는 퀘스트를 완료하면 3번 퀘스트의 우선순위를 하나씩 낮춰서 모두 클리어 했을떄 3번 퀘스트가 활성화 된다.  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class Main {     public static void main(String[] args) throws NumberFormatException, 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());                  ArrayList<Node>[] aLists = new ArrayList[N + 1];         int [] prio = new int[N + 1];                  for(int i = 0; i < N + 1 ; i ++) {             aLists[i] = new ArrayList<>();         }                  for(int i = 0; i < M; i ++) {               st = new StringTokenizer(br.readLine());               int front = Integer.parseInt(st.nextToken());               int back = Integer.parseInt(st.nextToken());               aLists[front].add(new Node(back));               prio[back]++;         }                           bfs(aLists, prio, N);     }     public static void bfs(ArrayList<Node>[] aLists, int[] prio, int N) {                  Queue<Integer> queue = new LinkedList<>();         for( int i = 1; i < N + 1 ; i++) {             if(prio[i] == 0) {                 queue.add(i);             }         } // 우선순위가 0순위인 사람 저장                  while(!queue.isEmpty()) {                          int vertax = queue.remove();             System.out.print(vertax + " ");                          for(Node node : aLists[vertax] ) {                 int adj = node.adj;                 prio[adj] --;                 if(prio[adj] == 0) { // 우선순위가 0이 될 경우                     queue.add(adj);                 }           }         }              } }     class Node{     int adj;          public Node(int adj) {         super();         this.adj = adj;     }      } Colored by Color Scripter

cs