[백준] 2252 줄 세우기 - Graph Theory / Java

• 문제 링크

2252번: 줄 세우기

 

• 풀이 과정

어떤 학생보다 키가 크므로 먼저 줄을 서야하는 학생의 수,

즉 외부 노드에서 들어오는 간선의 개수(진입 차수) 를 inDegree 배열에 저장하여 위상 정렬로 풀이한다.

예시로 학생 2 보다 큰 키의 학생 3, 4가 주어질 경우,

(4, 2), (3, 2) 의 입력이 주어지고 inDegree[2]++ 가 총 두번 수행되어 inDegree[2] = 2 로 초기화된다.

 

이 후 학생 i 에 대하여 inDegree[i] = 0, 즉 자신보다 먼저 줄을 서야할 학생이 없는 학생들을 큐에 삽입하고

큐가 비어있을 때까지 학생 node 가 poll() 되어 줄을 세우고 출력 버퍼에 저장한다.

 

이때 해당 학생이 특정 학생 v 보다 먼저 줄을 서야할 경우,

v 보다 먼저 줄을 서야할 학생 하나(node)가 감소했으므로 inDegree[v]-- 을 수행한다.

 

이런 과정을 통해 학생 v 의 들어오는 간선이 없다면(inDegree[v] == 0), 

즉 해당 학생보다 먼저 줄을 서야할 학생이 없으므로 큐에 삽입 및 반환하여 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<List<Integer>> list = new ArrayList<>();
        int[] inDegree = new int[n + 1];

        for (int i = 0; i <= n; i++)
            list.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            list.get(u).add(v);
            inDegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0)
                q.offer(i);
        }

        while (!q.isEmpty()){
            int node = q.poll();
            bw.write(node + " ");

            for (int v : list.get(node)) {
                inDegree[v]--;

                if (inDegree[v] == 0)
                    q.offer(v);
            }
        }

        bw.flush();
    }

}