[Boj_2252] 줄 세우기

📎 문제 링크

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

2252번: 줄 세우기

 

▸ 문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

▸ 입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

 

▸ 출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 3
• 🔔  문제 유형 : 그래프 이론, 위상 정렬, 방향 비순환 그래프
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 위상 정렬 알고리즘의 가장 기본 문제인 것 같다.
• 먼저, 위상 정렬에 사용 할 인접리스트와 각 노드의 진입차수를 저장 할 배열을 생성하여 값을 저장했다.
• 큐를 선언하여 진입차수가 0인 노드를 모두 담아주었다.
• 큐가 빌때까지 아래의 과정을 반복한다.
  • 큐에서 노드 하나를 꺼내고 정답 출력에 이용할 StringBuilder에 추가한다.
  • 현재 꺼낸 노드와 연결된 노드를 순회하며 연결된 노드의 진입차수를 1씩 감소시킨다.
  • 갱신된 노드의 진입차수가 0이라면 다시 큐에 넣어준다.

 

🔍 위상 정렬이란(Topology Sort) ?

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 경우 사용하는 알고리즘이다.
• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 나열하는 것을 의미한다.

진입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘 동작 과정

위상 정렬 알고리즘은 보통 큐를 이용하여 구현한다.

큐를 이용하여 구현한 위상 정렬 알고리즘의 동작과정은 다음과 같다

 

[ 동작 과정 ]

• 진입차수가 0인 노드를 큐에 넣는다.
• 큐가 빌 때까지 다음의 과정을 반복한다. 
  • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  • 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 

즉, 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

 

더 자세한 위상 정렬 알고리즘 정리는 클릭 !

 

✔ 최종 코드

메모리 : 44632 KB
시간 : 428 ms

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 학생의 수
        int m = Integer.parseInt(st.nextToken()); // 키를 비교한 횟수
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 위상 정렬에 사용할 그래프
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] edgeCout = new int[n+1]; // 위상 정렬에 사용할 진입차수 저장 배열
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            graph.get(num1).add(num2);
            edgeCout[num2]++;
        }
        
        Queue<Integer> que = new LinkedList<>();
        // 진입차수가 0인 값 큐에 넣기
        for (int i = 1; i <= n; i++) {
            if (edgeCout[i] == 0) que.offer(i);
        }

        while (!que.isEmpty()) {
            int node = que.poll();

            sb.append(node).append(" ");

            // 꺼낸 노드의 인접한 노드 찾기
            List<Integer> list = graph.get(node);
            for (int i = 0; i < list.size(); i++) {
                // 인접한 노드의 진입차수 감소
                edgeCout[list.get(i)]--;
                // 갱신된 노드의 진입차수가 0이면 큐에 담기
                if (edgeCout[list.get(i)] == 0) {
                    que.offer(list.get(i));
                }
            }
        }
        System.out.println(sb);
    }
}

 

👧🏻💭 : 나태병에 걸려 거의 한달만에 하는 포스팅이다.. 반성하고 더 부지런히 살아야지..! 뽜이팅 😂💪🏻