[코딩테스트] 백준 2252 자바

백준 2252

백준 2252 문제

해당 문제는 학생을 노드로, 키 비교 데이터를 에지라고 생각하고 "답이 여러 가지인 경우에는 아무거나 출력한다." 라는 문장을 보고 위상 정렬이라고 눈치를 챈다면 쉽게 풀 수 있는 문제이다.

import java.util.*;

public class Boj2252 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드의 수
        int m = sc.nextInt(); // 에지의 수
        // 인접 리스트 선언
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        // 진입 차수 배열 선언
        int[] inDegree = new int[n + 1];

        // 인접 리스트, 진입 차수 배열 초기화
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt(); // 시작 노드
            int end = sc.nextInt(); // 도착 노드
            list.get(start).add(end); // 시작 노드가 가리키는 도착 노드를 인접 리스트에 넣기
            inDegree[end]++; // 도착 노드를 가리키는 노드의 수 증가
        }

        // 위상 정렬 실행
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            // 진입 차수 배열의 값이 0인 노드를 큐에 넣기
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) { // 큐가 빌 떄까지 반복
            int now = queue.poll(); // 큐에서 노드 꺼내기
            System.out.print(now + " "); // 노드 출력
            for (int next : list.get(now)) { // 꺼낸 노드와 인접한 노드 하나씩 꺼내서
                inDegree[next]--; // 꺼낸 노드를 가리키는 노드의 수 감소
                if (inDegree[next] == 0) { // 감소된 노드의 수가 0이면
                    queue.offer(next); // 큐에 넣기
                }
            }
        }
    }
}

풀이

1. 노드의 수 n과 에지의 수 m을 입력 받는다.
2. 인접 리스트 list와 진입 차수 배열 inDegree를 선언한다.
3. m만큼 반복하면서 인접 리스트와 진입 차수 배열을 초기화하는데, 시작 노드 start와 도착 노드 end를 받아서 시작 노드가 가리키는 도착 노드를 시작 노드의 인접 리스트에 넣고 도착 노드를 가리키는 노드의 수를 inDegree[end]++를 통해 증가 시켜준다.
4. 이제 위상 정렬을 시작하는데 큐를 생성한 다음에 진입 차수 배열을 반복하면서 값이 0인 노드를 큐에 넣는다.
5. 이제 큐가 빌 때까지 반복하며 큐에서 노드를 꺼낸 다음에 출력을 해주고, 꺼낸 노드와 인접한 노드들을 돌면서 인접 노드를 가리키는 노드의 수 즉, inDegree[next]--를 통해서 감소시킨다.
6. 감소 시킨 후에 인접 노드의 진입 차수 배열의 값이 0이면 해당 노드를 큐에 넣는다.
7. 이 과정을 큐가 빌 때까지 반복하면 위상 정렬이 완료된다.

위상 정렬의 결과는 유일하지 않다.