[BOJ] 백준 2252- 줄 세우기 (자바)

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

위상정렬을 안다면 쉽게 풀 수 있는 문제

indegree 방식으로 문제 해결

풀이

1. 값을 저장해준다. List를 이용하여. (ArrayList 든 LinkedList든 상관 없뜸)

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

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

4. 끝

소스

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
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];
        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]++;
        }
        
        //-----------입력 부----------------------
        
        //Topological Sorting
        Queue<Integer> queue = new LinkedList<Integer>();
        //indegree가 0일때 큐에 넣는다. indegree는 자신을 가르키고 있는 화살표의 개수
        for(int i=1; i<=N; i++){
            if(indegree[i]==0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            System.out.println(queue.peek());
            int current = queue.poll();
            
            //자신이 가르키고 있는 좌표들을 방문하여 indegree값을 -1 해주고 만약 0이라면 큐에 넣어준다.
            for(int i=0; i<list[current].size(); i++){
                int next = list[current].get(i);
                indegree[next]--;
                if(indegree[next]==0){
                    queue.add(next);
                }
            }
        }
        
    }
 
}