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

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

2252번: 줄 세우기

문제 풀이

그래프 상에서 선수 관계가 존재하여 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 위상 정렬을 사용한다.

이 문제가 위상 정렬을 사용하는 대표적인 문제이다. 학생들간의 관계가 그래프 상에서 존재하고 두 학생의 키를 비교하여 누가 더 앞에 있는지 즉 선후 관계가 존재한다.

 

먼저 위상 정렬을 적용하기 위해선 진입 차수(inDegree)를 관리해야 한다. 따라서 인풋으로 들어오는 두 관계를 그래프에 적용시킴과 동시에 진입 차수도 같이 구해준다.

static List<Integer>[] graph;
static int[] inDegree;

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());

    graph[from].add(to);
    inDegree[to]++;
}

 

이후 위상 정렬을 실행한다. 먼저 진입차수가 0인 노드를 큐에 추가하여 선관계의 노드(학생)를 방문하고 연결된 자식 노드의 간선을 제거함으로써 자식 노드의 진입 차수를 줄인다. (간선을 제거하는 로직은 필요없음, 진입 차수만 줄여주면 됨)

이때 자식 노드의 진입 차수가 0이 되면 다음 방문 노드가 되어 큐에 추가된다.

static void topologicalSorting() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            Integer now = q.poll();
            List<Integer> children = graph[now];
            sb.append(now + " ");

            for (int i = 0; i < children.size(); i++) {
                Integer child = children.get(i);
                inDegree[child]--;

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

    }

이렇게 탐색 순서를 q에 넣음과 동시에 출력을 위한 StringBuilder에 넣어주고 위상 정렬이 끝났을 때 출력해주기만 하면 된다.

 

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b1766 {
    static List<Integer>[] graph;
    static int[] inDegree;
    static StringBuilder sb = new StringBuilder();

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        inDegree = new int[N + 1];
        graph = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph[from].add(to);
            inDegree[to]++;
        }

        topologicalSorting();
    }
    static void topologicalSorting() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            Integer now = q.poll();
            List<Integer> children = graph[now];
            sb.append(now + " ");

            for (int i = 0; i < children.size(); i++) {
                Integer child = children.get(i);
                inDegree[child]--;

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

        System.out.println(sb);
    }
}