[BOJ] 백준 1766- 문제집 (자바)

위상정렬 (Topological Sort) 의 가장 대표적인 문제

위상정렬을 처음 이해하고 문제를 푸는데 어려웠다. 머리속에 문제를 이해는 했는데 코드는 잘 안짜지는 느낌?

풀이

1. 값을 저장해준다. List를 이용하여. 

2. indegree가 0인 값을 큐에 모두 집어 넣는다.

3. 큐가 빌때까지 0인 값을 하나씩 빼서 그 다음 값을 다시 큐에 집어 넣는다. (단 그때 화살표 값인 Indegree를 하나씩 줄인다.)

4. 끝

의 과정 반복이다.

문제가 안풀리면 위상정렬을 공부하고 다시 보면 될것이다.

맞다. 이문제는 PriorityQueue를 사용해야한다. 왜냐하면 Queue에 같이 들어있을 때, 쉬운문제(번호가 작은 순)으로 풀어야 하기 때문

Queue를 사용하면 선입선출이기 때문에 값이 다르게 나온다.

소스

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] indegree = new int[N+1];
        ArrayList<Integer>[] list = new ArrayList[N+1];    //LinkedList 사용해도 상관 없음
        for(int i=1; i<=N; i++){
            list[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<M; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            list[x].add(y);    //리스트 안의 리스트에 값을 넣어준다.
            indegree[y]++;    //자신을 가르키고 있는 화살표의 갯수
        }
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
        for(int i=1; i<=N; i++){
            //indegree가 0인 값들 모두 큐에 넣어준다.
            if(indegree[i]==0){
                q.add(i);
            }
        }
        while(!q.isEmpty()){
            //indgree가 0인 값을 큐에서 뽑는다.
            int current = q.poll();
            System.out.print(current+" ");
            //뽑힌 곳에서 갈 수 있는 곳들을 검색하여 indegree를 -1한다.(자신을 가르키는 화살표가 하나 사라졌기 때문에)
            for(int i=0; i<list[current].size(); i++){
                int next = list[current].get(i);
                indegree[next]--;
                //indegree가 0이라면 큐에 넣는다.
                if(indegree[next]==0){
                    q.add(next);
                }
            }
        }
    }
 
}