[Algo Rhythm🕺💃] BOJ 10971 - 외판원 순회 2

💫문제 분석

도시들의 수를 $n$, 각 도시를 $C_i\ (1 \le i \le n)$, 그리고 $C_a$에서 $C_b$로 이동하는데 드는 비용을 $W_{a, b}$라고 하자. 이때 $W_{a, b} \ne W_{b, a}$일 수도 있고 $W_{a,b} = 0$ 이면 $C_a$에서 $C_b$로 이동할 수 없다.

 

우리는 외판원이 한 번 갔던 도시를 재방문하지 않을 때 어느 한 도시에서 출발해 $n$개의 도시를 모두 거쳐 다시 원래의 도시로 돌아올 때 드는 최소 비용을 구해야 한다. 이때 주의할 점이 외판원이 어느 도시에서 출발하는가는 중요하지 않다는 것이다. 왜냐하면 아래 그림과 같이 최소 비용으로 이동가능한 경로는 '원순열'의 형태를 띄기 때문이다.

 

따라서 이 문제는 최소 비용을 가진 원순열을 찾는 문제로 이해할 수 있다. 기본적으로 순열을 찾는 문제이기 때문에 backtracking을 사용하여 해결할 수 있다.

 

🔥문제 풀이

문제 분석에서 언급했듯이 이 문제는 최소 비용을 가진 원순열을 찾는 문제이기 때문에 어떤 도시에서 출발하는가는 중요하지 않다. 따라서, 임의로 출발 도시를 $C_1$으로 정했다.

 

그리고나서 나머지 도시들에 대해 backtracking을 실행하는데 다음 depth로 갈 수 있는 기준은 다음과 같다.

1. 방문한 적이 없다.
2. $W_{src, dest} \ne 0$

 

이때 불필요한 계산을 줄이기 위해 누적 비용이 이미 계산된 최소 비용보다 클 경우 backtracking 실행을 중단했다.

 

✨복잡도 분석

도시들의 수를 $n$이라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

 

⏰시간 복잡도 : $O(n!)$

• 최악의 경우 $x\ (1 \le x \le n)$의 도시를 방문한 뒤 $(n - x)$개의 도시들에 대해 backtracking을 실행해야 하기 때문에 $O(n!)$가 소요됨.

🏠공간 복잡도 : $O(n^2)$

• $W_{i, j}\ (1 \le i, j \le n)$을 저장하기 위해 $O(n^2)$가 소요됨.
• $C_i\ (1 \le i \le n)$의 방문여부를 저장하기 위해 $O(n)$이 소요됨.

 

🌈코드

	#include <cstdio>
	#include <climits>
	int w[10][10];
	bool visited[10];
	int n, mn = INT_MAX;
	void solve(int src, int acc, int size)
	{
	if(acc > mn) return;
	if(size == n)
	{
	if(w[src][0] && acc + w[src][0] < mn) mn = acc + w[src][0];
	return;
	}
	for(int dest = 0; dest < n; dest++)
	if(!visited[dest] && w[src][dest])
	{
	visited[dest] = true;
	solve(dest, acc + w[src][dest], size + 1);
	visited[dest] = false;
	}
	}
	int main()
	{
	scanf("%d", &n);
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &w[i][j]);
	visited[0] = true;
	solve(0, 0, 1);
	printf("%d\n", mn);
	return 0;
	}

view raw boj10971.cpp hosted with ❤ by GitHub

 

🌏문제 출처

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

10971번: 외판원 순회 2