C# 코딩테스트 강좌, 세일즈맨의 고민

안녕하세요, 여러분! 이번 포스팅에서는 C#을 활용한 코딩테스트 문제를 다뤄보겠습니다. 주제는 “세일즈맨의 고민”입니다. 이 문제는 알고리즘에서 많이 다루는 경로 최적화 문제로, 최적 경로 탐색 및 성능 개선의 중요한 개념을 이해하는 데 유용합니다.

문제 설명

한 세일즈맨이 N개의 도시를 방문해야 합니다. 각 도시 간의 거리 정보가 주어지며, 세일즈맨은 모든 도시를 한 번씩 방문한 후 다시 시작 도시로 돌아와야 합니다. 세일즈맨은 최소 거리를 통해 모든 도시를 방문하는 경로를 찾아야 합니다. 이 문제는 그러므로 주어진 도시들과 거리 정보를 기반으로 최적의 경로를 찾는 ‘외판원 문제(Travelling Salesman Problem, TSP)’에 해당합니다.

문제 정의

주어진 입력:
1. 도시는 N (1 <= N <= 10, 도시 수)
2. 각 도시 간의 거리 정보가 주어지는 2차원 배열 dist[n][n] (0 <= dist[i][j] <= 10^4)

출력:
1. 모든 도시를 통과하는 최소 거리 값

입력 예시


N = 4
dist = [[0, 10, 15, 20],
         [10, 0, 35, 25],
         [15, 35, 0, 30],
         [20, 25, 30, 0]]

이 예제의 설명:

이 배열에서 dist[i][j]는 도시 i에서 도시 j까지의 거리를 의미합니다. 세일즈맨은 모든 도시를 방문하고 최소의 거리를 통해 돌아와야 합니다. 예를 들어, 시작 도시에서 도시 1을 거쳐 도시 2로, 그리고 도시 3으로 이동 후 다시 돌아올 수 있는 다양한 경로가 존재합니다. 우리의 목표는 그 중에서 가장 짧은 거리의 경로를 찾아 출력하는 것입니다.

문제 해결을 위한 접근법

이 문제는 DFS(깊이 우선 탐색)를 활용한 백트래킹(Backtracking) 접근법으로 해결할 수 있습니다. 그러나 N이 10 이하로 제한되어 있기 때문에, 완전탐색(Brute Force) 기법을 사용해도 충분합니다. 이 문제는 어떤 경로를 갈지 결정하는 것이 가장 중요한데, 이는 주어진 거리 배열을 다루는 방법에 따라 결정됩니다.

알고리즘 단계

  1. 도시의 수를 기억합니다.
  2. 현재 도시를 기준으로 남은 도시들을 모든 경우의 수를 통해 순회합니다.
  3. 가장 적은 거리의 경로를 업데이트 합니다.
  4. 최종적으로 최소 거리를 반환합니다.

C# 코드 예시

using System;

class Salesman
{
    static int N;
    static int[,] dist;
    static bool[] visited;
    static int minCost = int.MaxValue;

    static void Main(string[] args)
    {
        N = 4;
        dist = new int[,] {
            { 0, 10, 15, 20 },
            { 10, 0, 35, 25 },
            { 15, 35, 0, 30 },
            { 20, 25, 30, 0 }
        };

        visited = new bool[N];
        visited[0] = true; // 시작 도시는 방문했습니다.
        DFS(0, 0, 1); // 첫 번째 도시 방문
        Console.WriteLine("최소 거리: " + minCost);
    }

    static void DFS(int currentCity, int cost, int count)
    {
        // 모든 도시를 방문한 경우
        if (count == N)
        {
            // 돌아오는 거리 계산
            cost += dist[currentCity, 0];
            minCost = Math.Min(minCost, cost);
            return;
        }

        // 다음 도시 탐색
        for (int nextCity = 0; nextCity < N; nextCity++)
        {
            if (!visited[nextCity])
            {
                visited[nextCity] = true; // 방문한 도시로 표시
                DFS(nextCity, cost + dist[currentCity, nextCity], count + 1);
                visited[nextCity] = false; // 백트랙킹
            }
        }
    }
}

코드 설명

위 코드는 DFS 백트래킹 기법을 사용하여 최소 거리를 찾는 예제입니다:

  1. Main 메서드: 도시 수와 거리 배열을 초기화 후 첫 번째 도시에서 DFS를 시작합니다.
  2. DFS 메서드: 현재 도시에서 방문하지 않은 도시를 재귀적으로 탐색합니다. 모든 도시를 방문했을 경우, 시작 도시로 돌아가는 경우를 추가하여 최소 비용을 갱신합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N!)입니다. 이는 모든 가능한 경로를 탐색하기 때문입니다. 하지만 N이 작기 때문에 실제로는 충분히 실행 가능합니다.

테스트 케이스

이제 이 알고리즘을 다양한 테스트 케이스로 검증해 보겠습니다:

// Test case 1
N = 3
dist = [[0, 10, 15],
         [10, 0, 20],
         [15, 20, 0]]
// Expected output: 35

// Test case 2
N = 5
dist = [[0, 20, 30, 10, 50],
         [20, 0, 40, 30, 50],
         [30, 40, 0, 30, 20],
         [10, 30, 30, 0, 20],
         [50, 50, 20, 20, 0]]
// Expected output: 90

결론

이번 코딩테스트 문제 풀이를 통해 세일즈맨의 고민을 해결했습니다. 알고리즘을 이해하고, C#을 통해 구현하면서 거리 배열을 어떻게 활용하는지 배웠습니다. 세일즈맨 문제는 알고리즘 경시 대회에서도 자주 출제되므로, 충분히 연습해보시길 바랍니다. 또한, 비슷한 문제를 다양한 접근법으로 풀어보는 것도 좋은 연습이 될 것입니다.

이번 포스팅이 유용했다면, 다음 포스팅도 기대해 주세요! 감사합니다.