자바 코딩테스트 강좌, 위상 정렬

안녕하세요! 오늘은 자바를 이용한 코딩 테스트에서 자주 등장하는 위상 정렬에 대해 알아보겠습니다. 위상 정렬은 Directed Acyclic Graph(DAG)에서 사용되는 알고리즘으로, 여러 개의 작업을 수행할 때 작업 간의 선후 관계를 고려하여 작업 순서를 결정하는데 매우 유용합니다.

1. 위상 정렬이란?

위상 정렬은 방향 그래프에서의 정점 순서를 나열하여 각 정점의 모든 선행 정점이 나열된 이후에 나오는 순서를 말합니다. 일반적으로 위상 정렬은 다음과 같은 경우에 사용됩니다:

  • 프로젝트 작업 중, 작업의 순서를 결정할 때 (예: 작업 A가 끝나야 작업 B를 시작할 수 있는 경우)
  • 학습 과정에서 수업의 순서를 결정할 때 (예: 선행 과목이 있어야 수강할 수 있는 경우)

2. 문제 설명

다음과 같은 문제를 해결해 보겠습니다:

3. 위상 정렬 알고리즘

위상 정렬을 수행하기 위해서는 ‘진입 차수’를 활용하는 방법과 ‘DFS’ 기반의 방법 두 가지가 있습니다. 여기서는 진입 차수 기반의 위상 정렬 방법을 설명하겠습니다.

3.1. 진입 차수 기반 위상 정렬

진입 차수 기반의 위상 정렬은 다음과 같은 단계로 이루어집니다:

  1. 그래프의 모든 정점의 진입 차수를 계산합니다.
  2. 진입 차수가 0인 정점을 큐에 넣습니다.
  3. 큐에서 정점을 하나씩 꺼내고, 해당 정점과 연결된 모든 정점의 진입 차수를 1 감소시킵니다.
  4. 진입 차수가 0이 된 정점은 큐에 추가합니다.
  5. 위 단계를 큐가 비어있지 않을 때까지 반복합니다.

4. 자바 코드 구현

위상 정렬 알고리즘을 Java로 구현해 보겠습니다. 아래는 문제 해결을 위한 Java 코드입니다.


import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 수업의 개수
        int M = scanner.nextInt(); // 관계의 개수

        List> graph = new ArrayList<>();
        int[] inDegree = new int[N + 1];
        
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 그래프 입력 처리
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            graph.get(A).add(B);
            inDegree[B]++;
        }
        
        // 진입 차수가 0인 노드를 큐에 담기
        Queue queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List result = new ArrayList<>();
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            for (int next : graph.get(current)) {
                inDegree[next]--; // 진입 차수 감소
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        // 순서가 결정되었는지 확인
        if (result.size() == N) {
            for (int i : result) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println(0);
        }
        
        scanner.close();
    }
}

5. 코드 설명

위의 Java 코드는 다음과 같은 방식으로 동작합니다:

  1. 입력을 받기 위해 Scanner를 사용하며, 수업의 개수 N과 관계의 개수 M을 읽습니다.
  2. 그래프와 진입 차수를 저장할 배열을 초기화합니다. 각 수업에 대한 그래프 정보를 리스트 형태로 저장합니다.
  3. M개의 관계를 입력 받으며, 각 수업 간의 관계를 그래프에 추가하고 진입 차수를 업데이트 합니다.
  4. 진입 차수가 0인 노드를 큐에 추가하여 시작합니다.
  5. 큐에서 정점을 꺼내고, 해당 정점과 연결된 모든 다른 정점의 진입 차수를 1 감소시킵니다.
  6. 만약 이 과정에서 진입 차수가 0이 되는 정점이 있다면 큐에 추가합니다.
  7. 예외 상황을 처리하며, 최종적으로 가능한 순서대로 수업을 출력합니다.

6. 예제 테스트

아래와 같은 입력을 테스트해 보겠습니다:


5 4
1 2
1 3
2 4
3 4

이 예제는 5개의 수업과 4개의 관계를 항상 포함하기 때문에 적절히 수행할 수 있습니다. 올바른 출력은 수업을 들을 수 있는 가능한 순서입니다.

7. 시간 복잡도

위상 정렬의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수(N)이고 E는 간선의 수(M)이므로 대규모 그래프에서도 효율적으로 작동합니다.

8. 결론

오늘은 자바를 이용한 위상 정렬 알고리즘에 대해 알아보았습니다. 이 알고리즘은 다양한 분야에서 유용하게 활용될 수 있으며, 코딩 테스트에서도 자주 등장하니 꼭 연습하시기 바랍니다. 복잡한 문제를 해결하는데 있어 위상 정렬이 큰 도움이 될 것입니다!

© 2023 자바 코딩 테스트 강좌