[BOJ] 백준 2252 줄 세우기

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

 Input 
3 2
1 3
2 3

 Output 

 1 2 3

N명(정점)의 학생들의 비교한 키가 일부 제공되었습니다.

(방식: 두 학생의 키를 비교 ← 방향성 그래프)

 

위상정렬 (Topological sort)  

위상정렬 (Topological sort)

 

구현

위상 정렬을 활용했으면 그 중 인접리스트 이용.

※ 해당 문제는 사이클을 형성하지 않는 Input Data이기에

     코드에 별도 사이클 유무에 따른 처리 X

---

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
     
    static Stack<Integer> stack;
    static ArrayList<ArrayList<Integer>> adList;
    static boolean[] visited, checked;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
         
        // 간선이 반드시 많은 것이 아니므로 인접 행렬 형태로 구현
        adList = new ArrayList<>();
        // 인덱스를 '1'부터 시작하기 위해 dummy data 넣어두기
        adList.add(new ArrayList<>());
        visited = new boolean[N+1];
        checked = new boolean[N+1];
        for(int i=1; i<=N; i++) {
            adList.add(new ArrayList<>());
        }
         
        // 정점의 간선을 연결한다.
        for(int i=1; i<=M; i++) {
            int targetVertex = Integer.parseInt(sc.next());
            int connectedVetex = Integer.parseInt(sc.next());
            adList.get(targetVertex).add(connectedVetex);
        }
         
        // 위상정렬 순으로 뽑기 위한 stack
        stack = new Stack<>();
         
        for(int i=1; i<=N; i++) {
            DFS(i);
        }
         
        while(!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        
    }
 
    private static void DFS(int i) {
        if(visited[i]) return;
         
        visited[i] = true;
 
        // 해당 정점과 이어진 모든 정점을 DFS할 때까지
        while(!adList.get(i).isEmpty()) {
            DFS(adList.get(i).remove(0));    
        }
        // 연결된 지점을 모두 돌아본 후이므로 스택에 넣어준다.
        if(!checked[i]) {
            checked[i] = true;
            stack.push(i);    
        }
    }
}