[Boj_2252] 줄 세우기

문제 설명

https://www.acmicpc.net/problem/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이 되면 해당 노드를 다시 큐에 넣어준다.

이 과정을 통해, 학생들의 앞뒤 관계를 지키면서 줄을 세울 수 있다.

 

코드

메모리 : 47052 KB
시간 : 384 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[] indegree = new int[n+1];
        
        // 비교 정보 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // a가 b 앞에 거야 한다 → a → b 간선
            graph.get(a).add(b);
            indegree[b]++; // b의 진입차수 증가
        }
        
        Queue<Integer> que = new LinkedList<>();
        
        // 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) que.offer(i);
        }

        // 큐가 빌 때까지 위상정렬 수행
        while (!que.isEmpty()) {
            int node = que.poll();
            
            // 위상정렬 결과 저장
            sb.append(node).append(" ");

            // 현재 노드와 연결된 노드들의 진입차수 감소
            for (int next : graph.get(node)) {
                indegree[next]--;

                // 진입차수가 0이 되면 큐에 삽입
                if (indegree[next] == 0) {
                    que.offer(next);
                }
            }
        }
        
        System.out.println(sb.toString());
    }
}

위상정렬(Topological Sorting) 알고리즘에 대한 자세한 설명이 궁금하다면 링크 클릭!