자바 코딩테스트 강좌, 외판원의 순회 경로 짜기

안녕하세요, 이번 블로그 포스트에서는 자바 코딩테스트에 자주 등장하는 문제 중 하나인 “외판원의 순회” 문제에 대해 깊이 있게 다뤄보겠습니다. 이 문제는 그래프 이론과 조합론의 기초를 다지는 데 매우 유용하며, 다양한 알고리즘 기법을 적용해 볼 수 있는 좋은 예시입니다.

문제 설명

외판원의 순회 문제는 다음과 같이 설명될 수 있습니다. 외판원은 주어진 도시들을 모두 방문하고 다시 출발 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다. 모든 도시는 서로 연결되어 있으며, 두 도시 사이의 거리가 주어집니다. 목표는 방문한 도시의 순회를 최소 비용으로 완수하는 것입니다.

입력

도시에 대한 수 N (2 ≤ N ≤ 10)
N x N 크기의 비용 행렬 C를 입력 받습니다. C[i][j]는 i번째 도시에서 j번째 도시로 가는 비용입니다. 만약 도시 i에서 j로 갈 수 없는 경우 C[i][j]는 무한대입니다.

출력

모든 도시를 한 번씩 방문하고 처음 도시로 돌아오는 최소 비용을 출력합니다.

문제 분석

이 문제는 NP-hard 문제로 분류되며, 일반적으로 완전 탐색 방법으로 해결할 수 있습니다. 하지만 N이 최대 10으로 제한되어 있으므로, 동적 프로그래밍(Dynamic Programming, DP)을 활용한 비트마스크 기법으로 효율적으로 해결할 수 있습니다. 비트마스크를 사용하면 각 도시의 방문 여부를 비트로 표현할 수 있게 되고, 이를 통해 모든 경로에 대한 최소 비용을 계산할 수 있습니다.

알고리즘 설계

문제를 해결하기 위한 기본 아이디어는 다음과 같습니다:

비트마스크를 사용하여 각 도시의 방문 상태를 나타냅니다.
재귀적인 방법으로 모든 가능한 경로를 탐색하면서 최소 경로를 계산합니다.
이미 계산한 최소 비용을 저장하여 중복 계산을 피하는 메모이제이션을 사용합니다.

주요 변수

N: 도시의 수
C[][]: 비용 행렬
cache: 메모이제이션을 위한 배열
allVisited: 모든 도시를 방문했는지를 확인하기 위한 비트마스크
start: 출발 도시

자바 코드 구현

아래의 코드는 주어진 알고리즘에 따라 외판원의 순회를 구현한 것입니다. 코드를 통해 각 단계가 어떤 식으로 진행되는지 확인해 보세요.


import java.util.Arrays;

public class TravelingSalesman {
    
    static int N; // 도시간의 수
    static int[][] C; // 비용 행렬
    static int[][] cache; // 메모이제이션을 위한 배열
    static final int INF = Integer.MAX_VALUE; // 무한대 값

    public static void main(String[] args) {
        // 예: 도시의 수 N = 4
        N = 4; 
        C = new int[][]{
            {0, 10, 15, 20},
            {5, 0, 9, 10},
            {6, 13, 0, 12},
            {8, 8, 9, 0}
        };

        // 메모이제이션 배열 초기화
        cache = new int[1 << N][N];
        for (int i = 0; i < (1 << N); i++) {
            Arrays.fill(cache[i], -1);
        }

        int result = tsp(1, 0); // 모든 도시를 방문한 상태에서 시작 도시 0
        System.out.println("최소 비용: " + result);
    }

    static int tsp(int visited, int pos) {
        // 기저 조건: 모든 도시를 방문한 경우
        if (visited == (1 << N) - 1) {
            return C[pos][0] == 0 ? INF : C[pos][0]; // 시작 도시로 돌아가는 비용
        }

        // 이미 계산된 경우
        if (cache[visited][pos] != -1) {
            return cache[visited][pos];
        }

        int answer = INF;

        // 모든 도시를 검사
        for (int city = 0; city < N; city++) {
            // 방문하지 않은 도시인 경우
            if ((visited & (1 << city)) == 0 && C[pos][city] != 0) {
                int newVisited = visited | (1 << city);
                int newCost = C[pos][city] + tsp(newVisited, city);
                answer = Math.min(answer, newCost);
            }
        }

        return cache[visited][pos] = answer; // 최소 비용을 저장
    }
}

코드 설명

메인 메소드: 예제로 도시 수와 비용 행렬을 초기화하고, TSP 함수를 호출하여 결과를 출력합니다.
tsp 메소드: 비트마스크와 현재 도시 정보를 바탕으로 재귀적으로 최소 비용을 계산합니다.
기저 조건: 모든 도시를 방문한 경우, 출발 도시로 돌아가는 비용을 리턴합니다.
메모이제이션: 이미 계산된 상태는 cache 배열에 저장하고 필요할 때 재사용하여 효율성을 높입니다.

결과

위의 코드는 주어진 도시와 비용 행렬에 대해 최소 비용을 계산해주는 프로그램입니다. 출력값은 모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 비용입니다. 이 코드를 활용해 자신만의 비용 행렬을 입력해 보고 결과를 확인하면서 알고리즘의 흐름을 이해하는 데 도움이 될 것입니다.

마무리

이번 강좌를 통해 외판원의 순회 문제를 동적 프로그래밍과 비트마스크를 활용하여 해결하는 방법을 배웠습니다. 이 문제는 코딩 테스트에서 자주 등장하며, 이를 해결하기 위한 기본적인 알고리즘 기법을 익히는 데 큰 도움이 될 것입니다. 다른 알고리즘 문제와 마찬가지로, 여러 가지 방법으로 문제에 접근할 수 있습니다. 다양한 해결 방법을 시도해 보며 스스로 알고리즘 능력을 향상시키시기 바랍니다.

다음 포스팅에서는 또 다른 문제를 다룰 예정이니 많은 기대 부탁드립니다. 질문이나 의견이 있으시면 댓글로 남겨주세요. 감사합니다!