[백준] 2252번 줄세우기 (JAVA)

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

2252번: 줄 세우기

 

---

 

위상정렬을 이용한 문제다.

정점 1의 간선이 정점 3에 방향그래프로 연결되어있다면 1을 처리해준 후 3을 정렬시켜 주면된다.

만약 정점 3을 향해 연결된 정점 2가 하나 더 있다면 정점 3은 정점 2 이후에 나열될 수 있다.

 

정점1과 정점2는 순서가 없으므로

 

1 -> 2 -> 3

2 -> 1 -> 3

 

둘다 가능하므로 나열하는 순서는 뒤바뀔 수 있다.

 

---

"자신에게 들어오는 간선이 없는 정점"을 확인하기 위해 int 배열을 만들어 준다.
ex) 0, 1, 2, 0, 0 // b에 들어오는 간선 1개, c에 들어오는 간선 2개

처음에 0인 정점을 q에 넣고, 큐를 순회하며 간선이 있다면 향하는쪽 정점을 1씩 줄여주면 된다.
정점이 0이 되면 큐에 넣는다. // 0이 될때는 딱 한번이다. inDegree 를 이미 세주었기 때문에.

---

코드 구현

 

import java.io.*;
import java.util.*;
 
public class TopologySort {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    static List<List<Integer>> list = new ArrayList<>();
    static Queue<Integer> q = new LinkedList<>();
    static int[] isZero;
 
    public static void main(String[] args) throws IOException {
        List<Integer> order = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int student = Integer.parseInt(st.nextToken());
        int lines = Integer.parseInt(st.nextToken());
        isZero = new int[student+1];
 
        // 0번은 사용하지 않음.
        for(int i = 0; i<=student; i++)
            list.add(new ArrayList<>());
 
        // 그래프 
        while(lines-- > 0){
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            ++isZero[second];
            list.get(first).add(second);
        }
 
        // 위상정렬
        for (int i = 1; i < isZero.length; i++) { // 모든 edge 확인
            if (isZero[i] == 0)
                q.add(i);
        }
 
        while (!q.isEmpty()) { // 현재 0인 edge
            int edge = q.poll();
            order.add(edge);
            List<Integer> v = list.get(edge);
            for (int e : v) { 
                isZero[e]--;
                if (isZero[e] == 0) { // 0이 됐을때 q에 넣는다.
                    q.add(e);
                }
            }
        }
        order.forEach((n) -> System.out.print(n + " "));
    }
}
 

 

 

 

---