[백준] 10971 - 외판원 순회 2

1. 문제

10971번: 외판원 순회 2

2. 개요

N개의 도시가 있다.

각 도시 사이에는 길이 있을수도 없을수도 있다.

한 외판원이 한 도시에서 출발해 N개의 도시를 모두 거쳐 첫 도시로 돌아오려고 한다.

이 때 가장 적은 비용을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 백트래킹으로 가능한 경우(0부터 N-1까지의 수들의 순열) 를 구한다.

구해진 순열의 맨 뒤에 순열의 맨 앞 원소를 추가한다.

최종적으로 완성된 순열은 외판원의 루트를 나타내게 되므로 1번 원소부터 해당 원소의 이전 원소와 graph를 이용하여 총 비용을 구한다.

구해진 총 비용과 현재까지 구한 최소 비용을 비교하여 갱신한다.

모든 경우에 대한 탐색을 마치고 답을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

graph = []
visited = [[False for i in range(N)] for j in range(N)]
answer = 1000000 * N + 1

for i in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

def BT(idx, l):
    global answer
    if idx == N:
        l.append(l[0])
        tmp = 0
        for i in range(1, N+1):
            if graph[l[i-1]][l[i]] == 0:
                return

            tmp += graph[l[i-1]][l[i]]

        answer = min(answer, tmp)

    for i in range(N):
        if visited[i] == True:
            continue

        visited[i] = True
        BT(idx + 1, l + [i])
        visited[i] = False

BT(0, [])
print(answer)

3-3. C#

namespace boj_10971
{
    internal class Program
    {
        static int N;
        static int[,] graph;
        static bool[] visited;
        static int answer;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            N = int.Parse(sr.ReadLine());
            graph = new int[N, N];
            visited = new bool[N];
            answer = 1000000 * N + 1;

            for (int i = 0; i < N; i++)
            {
                string[] input = sr.ReadLine().Split();

                for (int j = 0; j < N; j++)
                {
                    graph[i, j] = int.Parse(input[j]);
                }
            }

            BT(0, new List<int>());
            sw.WriteLine(answer);
            sw.Close();
        }

        static void BT(int idx, List<int> results)
        {
            if (idx == N)
            {
                results.Add(results[0]);
                int tmp = 0;
                for (int i = 1; i < N + 1; i++)
                {
                    if (graph[results[i - 1], results[i]] == 0)
                        return;

                    tmp += graph[results[i - 1], results[i]];
                }

                answer = (int)MathF.Min(answer, tmp);
            }

            else
            {
                for (int i = 0; i < N; i++)
                {
                    if (visited[i])
                        continue;

                    visited[i] = true;
                    BT(idx + 1, results.Append(i).ToList());
                    visited[i] = false;
                }
            }
        }
    }
}