[C++] 백준 10971: 외판원 순회 2

문제 이해

- Traveling Salesman Problem (TSP)라고 불리는 문제이다.

- 1번부터 N번까지 도시에 번호가 매겨져있다.

- 도시들 사이에는 길이 존재하는데, 이는 없을 수도 있다.

- 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획중이다.

- 단, 한 번 갔던 도시로는 다시 갈 수 없다.

※ 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외이다.

- 가장 적은 비용을 들이는 여행 계획의 비용을 출력하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 256MB

 

<입력>

N: 도시의 수 (2 ~ 10)

W[i][j]: i번 도시에서 j번 도시까지 가기 위한 비용 (1 ~ 1,000,000, 10^6)

- 비용은 비대칭적이다.

- W[i][i]는 항상 0이다.

- i번 도시에서 j번 도시로 갈 수 없는 경우 w[i][j] = 0이다.

※ 입력은 항상 순회가 가능하도록 주어진다.

 

<출력>

- 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력하라.

 

 

문제 풀이

외판원 순회 알고리즘에 대해 잘 알지 못해 지레 겁먹고 인터넷 풀이를 바로 봤다.

 

 

찾아보니 N의 크기가 핵심이었는데, N이 10이하이므로 10!로 해결이 돼,

브루트포스+백트래킹으로 모든 경우의 수를 비교해서 푸는 문제였다.

 

 

코드를 작성하며 주의할 점은

마지막 도시에서 출발 도시로 돌아갈 때

만약 갈 수 없는 경우, 즉 값이 0일때는 초기화를 해줘서는 안된다는 것이다.(갈 수 없으므로)

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int map[15][15];
int n;
bool visited[15];
int first;
int mincost = 987654321;

void dfs(int start, int cost, int depth){
    if(depth == n-1){
        if(map[start][first] != 0){
            mincost = min(mincost, cost + map[start][first]);
        }
    }

    visited[start] = true;
    for(int i = 0; i < n; i++){
        if(map[start][i] != 0 && !visited[i]){
            visited[i] = true;
            dfs(i, cost + map[start][i], depth+1);
            visited[i] = false;
        }
    }
    visited[start] = false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin>>map[i][j];
        }
    }

    for(int i = 0; i < n; i++){
        first = i;
        dfs(i, 0, 0);
    }

    cout<<mincost;
    return 0;
}