[백준_10971번] 외판원 순회 2

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

10971번: 외판원 순회 2

[문제]

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

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

 

[코드]

import java.util.*;

public class BaekJoon_10971 {
	static int[][] map;
	static int n,min=Integer.MAX_VALUE;
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		visited=new boolean[n];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=sc.nextInt();
		
		// 시작점을 바꿔가며 순회
		for(int i=0;i<n;i++)
			dfs(i,i,0,0);
		
		System.out.println(min);
	}
	
	// 백트래킹
	static void dfs(int start, int now, int depth, int cost) {
		// 모든 도시를 순회했고, 다시 시작점으로 돌아왔다면 최솟값 갱신
		if(depth==n&&start==now) {
			min=Math.min(cost, min);
			return;
		}
		
		// 순회할 도시 탐색
		for(int i=0;i<n;i++) {
			// i번째 도시와 이어져있지 않다면 넘어간다.(자기 자신 포함)
			if(map[now][i]==0)
				continue;
			
			// 현재 도시를 방문하지 않았고, 다음 순회할 i번째 도시와 연결되어 있다면
			if(visited[now]==false&&map[now][i]>0) {
				visited[now]=true; // 현재 도시 방문처리
				cost+=map[now][i]; // 비용 증가
				dfs(start,i,depth+1,cost); // now를 i번째 도시로 갱신하고, 깊이를 1 증가시킨다.
				// 다음 탐색을 위해 초기화
				visited[now]=false;
				cost-=map[now][i];
			}
		}
	}
}

 

[고찰]

 이번 문제는 시작 도시를 바꿔가며 다른 도시를 순회했을 때 최솟값을 찾는 백트래킹 문제이다. 처음에는 dfs 함수의 매개변수로 무엇을 주어야 할지 헷갈렸다. 이번 문제는 순회를 시작한 도시로 다시 돌아와야 하기 때문에 시작 도시를 저장하는 start 변수와 현재 순회하고 있는 도시 now를 매개변수로 가져가야 한다는 것을 깨달았다. 따라서 재귀호출은 탐색 도시의 개수를 count하는 depth 변수가 도시의 개수 n과 같아졌고, now 변수가 start 값과 같아졌을때 종료해야 한다. 또한 다음 탐색할 now 도시를 정할때는 백트래킹 방법을 사용하여 다음 도시와 연결되어 있고, 현재 도시를 탐색하지 않았다면 해당 도시를 선택하는 방법으로 해결할 수 있다.