[C++/BOJ] 10971 : 외판원 순회 2 (완전탐색, dfs, Backtracking)

https://www.acmicpc.net/problem/10971

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

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

---

 

백준 실버2.

Traveling Salesman Problem, 줄여서 TSP

이거 알고리즘 수업시간에 배웠던 것 같음

 

TSP는 NP-Hard 문제의 일종이다. 간단히 말하면 그냥 풀기 어려운 문제라는 뜻이다

 

 

main ideas

 

1. 일단 무지성 dfs...하면 되는데, 백트래킹을 위해 dfs 다음에 상태를 기존으로 돌려놓는 코드가 있어야 함.

그리고 모든 시작점을 고려해야하기 때문에 완전탐색 -> 재귀 진입할때도 반복문 필요함

 

2. 방문하려는 다음 마을에 방문한적이 있거나, 가는 경로가 없다면 continue

 

3. 마지막 마을에서 출발지로 돌아갈 수 있어야 하나의 경로로 인정됨. (순회 가능)

 

4. 최소값은 선언 시 INT_MAX로 해놓고, 순회하면서 최솟값을 저장하기

 

 

 

나의 풀이

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int n;
int w[10][10] = {0};
int visited[10] = {0};
int answer = INT_MAX;

void travel(int start, int now, int cnt, int sum){
    if(cnt == n){
        if(w[now][start] == 0) return; // 마지막 마을에서 출발지로 못 돌아갈때
        if(answer > sum + w[now][start]) answer=sum+w[now][start]; // 최솟값 대체
        return;
    }

    for (int i = 0; i < n; ++i){
        if(visited[i]==1 || w[now][i]==0) continue; // 마을방문 or 길없을때
        visited[i] = 1;
        travel(start, i, cnt + 1, sum + w[now][i]);
        visited[i] = 0; // 탐색 종료 후 다른경로로 탐색을 위해 되돌려놓기
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    for (int i = 0; i < n; ++i){
        visited[i] = 1;
        travel(i, i, 1, 0);
        visited[i] = 0; // 다음 반복을 위해 되돌려놓기
    }
    cout << answer;
}