[Algorithm] 백준 2252번(BOJ 2252) 줄 세우기 문제풀이 (Java)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 2252번 줄 세우기 문제를 풀어보겠습니다.

 

1. 문제 설명

문제를 설명하기에 앞서 아래 링크로 가셔서 문제를 먼저 읽고 와주시길 바랍니다.

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

 

해당 문제는 학생들을 키 순서대로 세우면 되는 문제입니다.

이를 위해 문제에서는 어떤 학생이 어떤 학생 앞에 서야 하는지 조건도 주고 있습니다.

가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다.

그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다.

그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상 정렬(Topological Sort)이 있습니다.

위상 정렬(Topological Sort)은 그래프에서 선후관계 조건이 있을 때 이를 고려해서 노드의 순서를 정렬할 수 있습니다.

자세한 내용은 제가 포스팅한 내용이 있으니 확인해주시기 바랍니다.

[Algorithm] 위상 정렬(Topological Sort)을 Java로 구현해보자!!

 

위의 문제에서는 학생 각각을 노드로 보고 주어진 조건을 간선이라고 생각하면 위상 정렬을 통해 학생들을 키 순서대로 세울 수 있습니다.

문제의 내용을 그래프로 표현할 수만 있다면 위상 정렬을 사용해서 쉽게 풀어낼 수 있습니다.

그럼 코드로 작성해보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BOJ_2252 {

    // 백준온라인저지 2252번 줄 세우기 Java풀이
    public static void main(String[] args) throws IOException {

        // 입출력에 사용할 객체
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 주어진 정보 받기
        String[] info = br.readLine().split(" ");

        // 학생의 수
        int N = Integer.parseInt(info[0]);
        // 학생의 키 비교한 횟수
        int M = Integer.parseInt(info[1]);

        // 위상정렬에 사용할 진입차수 저장 배열
        int[] edgeCount =new int[N + 1];
        // 위상정렬에 사용할 그래프 2차원 리스트로 구현
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= N+1; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 2차원 리스트의 인덱스가 학생번호
        // 주어진 키 비교정보에 따라 2차원 리스트 정보 초기화
        // 리스트 초기화 하면서 진입차수배열 값 초기화
        for (int i = 0; i < M; i++) {
            String[] temp = br.readLine().split(" ");
            graph.get(Integer.parseInt(temp[0])).add(Integer.parseInt(temp[1]));
            edgeCount[Integer.parseInt(temp[1])]++;
        }

        // 위상정렬에 사용할 큐
        Queue<Integer> q = new LinkedList<>();

        // 진입차수가 0인 값 큐에 넣기
        for (int i = 1; i < edgeCount.length; i++) {
            if (edgeCount[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 학생번호 꺼내기
            int studentNo = q.poll();

            // 꺼낸 학생번호 출력값에 저장
            bw.write(String.valueOf(studentNo) + " ");

            // 꺼낸 학생번호의 키 비교한 정보 가져오기
            List<Integer> list = graph.get(studentNo);

            // 키를 비교한 정보의 개수 만큼 반복문 실행
            for (int i = 0; i < list.size(); i++) {
                // 해당 학생보다 뒤에 서야하는 학생의 정보 가져오기
                int temp = list.get(i);
                // 뒤에 서야하는 학생의 진입차수 감소
                edgeCount[temp] -- ;
                // 감소한 진입차수가 0이면 큐에 학생번호 넣기
                if (edgeCount[temp] == 0) {
                    q.offer(temp);
                }
            }
        }

        // 출력
        bw.flush();
    }
}

 

작성한 코드의 라인마다 모두 주석을 적어놓았습니다.

위상 정렬을 구현할 수 있다면 어렵지 않은 문제이지만, 반대로 위상 정렬에 대해서 아예 모르신다면 위상 정렬에 대해서 먼저 학습하신 후에 코드를 보시면 더 쉽게 이해하실 수 있을 거라 생각합니다.

감사합니다.

---