백준 2252 줄 세우기 Java

위상 정렬을 사용해서 풀어야 하는 줄 세우기 문제이다.

 

위상 정렬은 DAG에서 방향성을 거스르지 않고 정점들을 나열하는 알고리즘이다.

DAG는 Direct Acyclic Graph로 사이클 없는 방향 그래프를 말한다.

위상 정렬에 관한 내용은 아래의 링크에서 친절하고 자세히 설명해 준다.

https://jason9319.tistory.com/93

Topological Sort(위상 정렬)

 

문제의 내용은

두 학생의 번호 A, B가 주어지고

A가 B앞에 서야 한다는 의미로 해석된다.

주어진 조건을 만족하는 줄을 세운 결과를 출력하면 된다.

답은 여러개여도 그중 하나를 출력하면 된다.

 

위상 정렬을 하는 방법 중에서 dfs를 사용하는 방법을 선택해서 풀었다.

위상 정렬을 알고 있다면 쉽게 풀 수 있는 문제이다.

 

A학생이 B학생 앞에 선다면

A -> B

C학생이 A학생 앞에 선다면

C -> A -> B

이처럼 입력받은 조건을 방향 그래프로 만들어주고

위상 정렬을 해준 결과를 출력하면 된다.

 

조금 더 자세히 말하면

입력받은 조건으로 방향 그래프를 만들고

for문으로 1부터 N까지 dfs를 호출하고

dfs 메소드 안에서 for each문을 빠져나온 정점은

스택에 넣어진다.

마지막으로 스택을 역순으로, pop을 하며 출력을 하면

dfs를 사용한 위상 정렬이 완성된다.

 

이 문제가 위상정렬을 사용해야 하는 것인지 캐치하기는 어려울 것 같다.

위상 정렬을 다시 한번 복습해보도록 하자!

 

import java.io.*;
import java.util.*;
 
 
public class Q2252 {
    public static Stack<Integer> s = new Stack<>();
    
    public static void dfs(List<Integer>[] list, boolean[] visited, int v) {
        visited[v] = true;
        for(int k : list[v]) {
            if(!visited[k]) {
                dfs(list, visited, k);
            }
        }
        s.push(v);
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        List<Integer> [] list = new ArrayList[n+1];
        boolean [] visited = new boolean[n+1];
        
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
        }
        for(int i=1; i<=n; i++) {
            if(!visited[i])
                dfs(list, visited, i);
        }
        StringBuilder sb = new StringBuilder();
        while(!s.isEmpty()) {
            sb.append(s.pop()+" ");
        }
        System.out.print(sb.toString());
    }
 
}