자바 코딩테스트 강좌, 빌딩 순서 구하기

본 글에서는 자바 코딩테스트를 대비하기 위한 알고리즘 문제를 하나 풀어보겠습니다. 주제는 “빌딩 순서 구하기”입니다. 이 문제는 다양한 분야에서 활용될 수 있는 그래프 탐색 알고리즘과 정렬 알고리즘을 결합한 문제입니다. 문제를 해결하기 위해 필요한 이론적 배경 및 코드 구현 방법에 대해 자세히 설명하겠습니다.

문제 설명

당신은 도시의 여러 빌딩을 건설할 계획을 세우고 있습니다. 각 빌딩은 서로의 의존성에 따라 순서를 가지고 있습니다. 즉, 빌딩 A가 빌딩 B보다 먼저 건설되어야 하는 경우, A -> B로 의존성이 나타납니다. 이러한 규칙에 따라 모든 빌딩의 건설 순서를 정하는 문제를 해결해야 합니다.

다음은 입력으로 주어지는 빌딩의 개수 N과 의존성 정보입니다. 당신은 모든 빌딩의 건설 순서를 출력해야 합니다.
예를 들어, 다음과 같은 의존성이 주어졌다고 가정해봅시다:

이 입력은 5개의 빌딩이 있으며, 다음과 같은 의존성이 존재함을 의미합니다.
1번 빌딩은 2번 빌딩이 먼저 건설되어야 하고, 1번은 3번, 2번은 4번, 3번은 5번이 먼저 건설되어야 합니다.
이 경우, 가능한 한 빌딩들의 건설 순서는 다음과 같습니다:

            1, 2, 3, 4, 5 또는 1, 2, 3, 5, 4 등.

문제 해결을 위한 전략

이 문제를 해결하기 위해서는 그래프 이론에서의 위상 정렬(Topological Sorting) 개념을 활용할 수 있습니다. 위상 정렬은 방향 그래프에서 모든 정점(노드)을 유향 간선의 방향에 따라 나열하는 것입니다. 이때, 간선 A -> B가 있을 경우 A는 B보다 앞에 나와야 합니다.

알고리즘의 주요 단계는 다음과 같습니다:

그래프를 인접 리스트 형태로 구현합니다.
각 노드의 진입 차수(in-degree)를 계산합니다.
진입 차수가 0인 노드를 시작으로 큐에 추가합니다.
큐에서 노드를 하나씩 꺼내며 순서를 기록하고, 그 노드에 연결된 다른 노드의 진입 차수를 감소시킵니다. 이때, 진입 차수가 0이 된 노드는 다시 큐에 추가합니다.
모든 노드가 처리될 때까지 반복합니다.

자바 구현 코드

위에서 설명한 알고리즘을 바탕으로 자바로 코드를 구현해보겠습니다. 아래는 위상 정렬을 수행하는 자바 코드입니다.

                
public class BuildingOrder {
    import java.util.*;

    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]++;
        }
        
        // 위상 정렬을 수행하기 위해 과정 구현
        StringBuilder result = new StringBuilder();
        Queue queue = new LinkedList<>();

        // 진입 차수가 0인 노드 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.append(current).append(" ");

            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 결과 출력
        System.out.println("빌딩 건설 순서: ");
        System.out.println(result.toString().trim());
        scanner.close();
    }
}

위 코드는 먼저 빌딩의 개수와 의존성을 입력받고, 이를 기반으로 그래프와 진입 차수를 초기화합니다. 그 후, 위상 정렬을 통해 건설 순서를 결정하고 출력합니다.

입출력 예제

예제 입력

예제 출력

            빌딩 건설 순서: 
            1 2 3 4 5 또는 1 2 3 5 4

심화 학습

위상 정렬 알고리즘은 많은 실제 상황에서 사용될 수 있습니다. 예를 들어, 프로젝트 일정 관리, 컴파일러의 문법 분석, 그리고 여러 과정의 선후 관계가 있는 문제를 해결하는 데 유용합니다. 이러한 알고리즘을 이해하고 잘 활용한다면, 코딩 테스트는 물론 다양한 분야에서의 문제 해결에도 큰 도움이 될 것입니다.

연습 문제:

1. 위상 정렬을 사용하여 다음과 같은 그래프에 대한 건설 순서를 구해보세요.

2. 다음의 의존성을 구현하고, 그래프를 시각화하여 어떤 문제가 발생할 수 있는지 고민해보세요.