[백준 10971] 외판원 순회 2 (DFS)

• 안녕하세요. BlockDMask 입니다.

• 오늘의 문제 풀어보겠습니다.

0. 제목

• 백준 10971 외판원 순회 2

• BOJ 10971 외판원 순회 2

1. 문제 설명

• 외판원 순회 문제는 영어로 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. 풀이 과정

• 각각의 도시에서 시작해서 전체 탐색을 하는 방식으로 깊이 우선 탐색(DFS)을 통해서 구했습니다.

• 한도시 a에서 시작해서 다른 도시 b로 가게 되면 [a,b]를 들르고 도시를 방문했다는 표시를 배열 check에 하게 됩니다.

• 도시를 가는 길의 비용(가중치)를 계속 변수 sum 에 더하면서 탐색을 진행 합니다.

• 재귀를 통한 탐색을 진행하다가
  종료조건을 만나게 되면 return 하게 됩니다.
  여기서 종료 조건은 모든 도시를 방문했고, 다시 처음의 도시로 돌아 온 경우를 말합니다.

• ** 전체 탐색이라 했지만, 경로의 최소 값을 구하는 것 이므로 도시의 비용인 sum이 최소값인 m 보다 큰 경우는 더이상 탐색을 진행하지 않았습니다.

• 아래 if(sum<=m) 부분의 조건문을 사용하지 않으면 시간이 1200MS 대로 엄청나게 뛰게 됩니다.

3. 소스 코드

//https://www.acmicpc.net/problem/10971
//BOJ_10971_TravelingSalesmanProblem
 
#include<iostream>
#include<cstdio>
using namespace std;
 
int arr[11][11];  //map.
int check[11];  //도시를 방문 했는지 check
int n;          //n.
int m = 987654321;  //순회의 최소 비용
 
void input(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &arr[i][j]);
        }
    }
}
 
void dfs(int start, int y, int sum, int cnt){
    //모든 도시를 들렀고(cnt==n) && 다시 스타트 도시로 온 경우(start==y)
    if(cnt == n && start == y){
        if(m > sum) m = sum;
        return;
    }
 
    for(int x=0; x<n; x++){
        if(arr[y][x] == 0) continue;    //연결 되지 않은 경우(자기자신포함)
 
        //방문 하지 않고 y,x가 0보다 큰 경우
        if(!check[y] && arr[y][x] >0) {
            check[y] = true;    //방문 체크
            sum+=arr[y][x];
 
            if(sum <= m){   //sum이 m 보다 작은 경우만 탐색 진행
                //[1,2]이었으면 [2,-]로 보내줌.
                dfs(start, x, sum, cnt+1);
            }
 
            //방문한 기록과 합 초기화
            check[y] = false;
            sum-=arr[y][x];
        }
    }
}
 
void solution(){
    for(int y=0; y<n; y++){
        //각각의 점(도시)에서 시작하는 경우
        dfs(y, y, 0, 0);
    }
}
 
 
void output(){
    printf("%d", m);
}
 
int main(void){
    input();
    solution();
    output();
    return 0;
}
 

4. 인증

• if 조건 있을때.

• if 조건문 없이 전체 탐색을 그대로 진행했을때.

• 문제 출처 : https://www.acmicpc.net/problem/10971

• 감사합니다.