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

10971번: 외판원 순회 2

[문제 설명]

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	37582	13566	8013	33.729%

문제

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

출력

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

예제 입력 1 복사

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1 복사

35

---

[문제 풀이]

문제를 푸려고 봤더니 예전에 풀었던 문제였다.

풀어봤던 문제였지만 답을 맞추는데까지 꽤 시간이 걸렸다.

문제 내용을 보니 DFS를 사용해서 문제를 풀어야한다는건 기억이 났다.

 

다른 DFS 문제와 동일하게 모든 경우의 수를 탐색하면 되는 문제다.

다만 조금 헷갈렸던 부분은 처음 시작한 도시로 다시 돌아와야 한다는 점이였다.

도시 방문 여부를 vector로 따로 체크하고 있는데

만약 시작하는 도시를 true로 체크해버리고 시작하면 로직중에 다시 첫번째 도시로 돌아올 수 없었다.

 

그래서 생각이 났던 방법은 처음 시작하는 도시를 체크하지 않고 로직을 시작하여

방문한 도시의 개수가 전체 도시의 수만큼이고, 시작한 도시로 돌아왔을때가

우리가 원한 모든 도시를 방문하고 돌아온 순간이기에 그순간의 비용을 이 전에 계산해둔 최소 비용과 비교하여 저장하면 된다.

 

계산 중에 시간을 단축하기 위해서는 현재 계산되고 있는 값이 현재까지의 최소비용보다 작은 경우에만 탐색하도록 하면 좀 더 빠르게 답을 구할 수 있다.

 

문제 풀고 정답을 확인한 다음.. 저장해놨던 예전 코드를 봤더니.. 거의 똑같았다..

풀었던 경험에 의존해서 푼건지... 풀어봤던 문제는 어렴풋이 기억이 나는거같다.. 

더 많은 문제를 풀어 경험으로 만들어놔야겠다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> v;
vector<bool> isvisited;
int gCount;
int gMin = 0x7fffffff;
int gSum;
/* 
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
예제 출력 1 
35 


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

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

*/
void dfs(int start, int now)
{
    if(gCount == n && start == now)
    {   
        gMin = min(gMin,gSum);
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(i == now || isvisited[i] || v[now][i]==0) continue;
        isvisited[i] = true;
        gSum += v[now][i];
        if(gSum < gMin)
        {
            gCount++;
            dfs(start,i);
            gCount--;
        }
        gSum -= v[now][i];
        isvisited[i] = false;
    }
}


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

    cin >> n;
    v = move(vector<vector<int>>(n,vector<int>(n,0)));
    isvisited = move(vector<bool>(n,0));    
    for(int i =0 ; i < n; i++)
    {
        for(int j =0; j < n; j++)
        {
            cin >> v[i][j];
        }
    }

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

    cout << gMin << "\n";
}