[백준 10971] 외판원 순회2

문제

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

10971번: 외판원 순회 2

 

설계

 

설계방향성:

이 문제는 결국 이동가능한 경로에 대한 순열을 찾는 문제이다.

(∵ 문제에서 주어진 인접행렬은 W[i][j] != W[j][i]  양방향 그래프이다. 즉, 경로 [1, 2, 3] != [1, 3, 2] 이기 때문에 조합이 아닌 순열을 구해야하는 것이다.)

 

dfs로 접근

순열은 dfs탐색으로 구할 수 있다. 하지만, dfs탐색으로 순열을 구할 경우 Input Size에 따라 경우의 수가 너무 많기 때문에 시간초과가 발생할 수 있다. dfs탐색으로 접근이 가능한지 먼저 생각해봐야할 것이다.

 

• Worst Case: 최악의 경우 도시의 개수N은 10개가 된다. 이 경우, 10P10 = 3628800 경우의 수가  존재한다. 충분히 연산할 수 있는 횟수이고, 실제로는 적절한 Pruning으로 가지치기 (이동가능한 경우만 탐색)할 것이기 때문에 실제 연산횟수는 더 적을 것이다. 

 

 

State Space Tree 설계

dfs로 접근하는 문제는 어떤식으로 재귀적 탐색을 수행할지, 알고리즘 로직의 흐름을 쉽게 파악하기 위해 State Space Tree를 사전에 설계하면 좋다.

 

 

SST를 만듦으로서,

"어떤식으로 재귀적 탐색이 이루어지는지"에 관한 Recursive Case와

"언제 재귀적 탐색이 종료되고 종료시점에 해야하는 작업"에 관한 Base Case에 대해 파악할 수 있다.

 

Recursive Case

• 1 ~ N번 도시에 대해서 재귀적 탐색
• 단, 1)방문안한 도시만 탐색,  2)이동가능한 경우만 탐색

Base Case

• depth == N일때 종료
• depth == N에 도달했다는 것은 어떠한 임의의 경로 Path = [1, 2, 3, 4, 0]을 구했다는 것. (경로의 처음은 시작도시)   
• 마지막도시 -> 출발도시 이동가능한 경우에만 Path의 마지막원소 0을 출발도시로 채우고
• 해당 Path에 대한 거리를 구하고 최소비용을 갱신하면 될 것이다.

 

 

 

전체코드

public class Main {
	static int[][] board;
	static boolean[] visit;
	static int[] path;
	static int N;
	static long minEdge = Long.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		board = new int[N+1][N+1];
		visit = new boolean[N+1];
		path = new int[N+1];
		for (int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=1; j<=N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//"어느 한 도시"에서 출발이므로, 출발도시: 1~N번도시 모두 조사
		for (int startCity=1; startCity<=N; startCity++) {
			
			//이전에 조사하며 사용한 경로(path), 방문여부(visit) 초기화
			Arrays.fill(visit, false);
			Arrays.fill(path, 0);
			
			//첫번째 경로는 시작도시로 고정
			path[0] = startCity;
			visit[startCity] = true;
			
			//경로탐색
			dfs(1, startCity, startCity);
		}
		System.out.println(minEdge);
	}
	private static void dfs(int depth, int now ,int startCity) {
		
		//base case
		if (depth == N) {
			
			//경로(path)의 마지막도시 -> 출발도시 가능한 경우만 비용 및 최소비용 갱신
			int lastCity = path[path.length-2];
			if(board[lastCity][startCity] != 0) {
				path[path.length-1] = startCity;
				result();
				return;
			}
			return;
		}
		
		//recursive case
		for (int i=1; i<=N; i++) {
			if(!visit[i] && board[now][i]!=0) {
				visit[i] = true;
				path[depth] = i;
				dfs(depth+1, i, startCity);
				visit[i] = false;
			}
		}
		
	}

	private static void result() {
		int sumEdge = 0;
		
		for (int i=0; i<path.length-1; i++) {
			int from = path[i];
			int to = path[i+1];
			
			sumEdge += board[from][to];
		}
		
		minEdge = Math.min(minEdge, sumEdge);
	}
}

 

 

새로 알게된 사실

※어느 도시에서 출발하던 최소비용은 모두 같다

문제에 "어느 한 도시"에서 출발한다고 언급되어 있기 때문에 위의 코드에선 출발도시: 1 ~ N에 대해 모두 조사를 했었다. 문제에 대해 다시한번 생각해보자.

이 문제는 결국 최소비용을 갖는 Cycle을 찾는 문제이다.

Cycle이기 때문에 우리가 찾은 Cycle에 대해 출발도시는 1번도시가 될 수도, 2번도시가 될 수도, ... , N번도시가 될 수도 있다.

또한, 모든 경로에 대해 조사하는 것이기 때문에 출발도시가 몇 번 도시가 되었든, 경로 조사 중 언젠가 우리가 이전에 이미 찾은 최소비용에 해당하는 Cycle을 조사하게 된다.

 

이에 따라, 메인함수의 dfs 탐색시작 부분의 코드는 다음과 같이 변경된다.

...

//for (int startCity=1; startCity<=N; startCity++) {
			
//			Arrays.fill(visit, false);
//			Arrays.fill(path, 0);
			
//			path[0] = startCity;
//			visit[startCity] = true;
			path[0] = 1;
			visit[1] = true;

			//경로탐색
//			dfs(1, startCity, startCity);
			dfs(1, 1, 1);
//}

...

 

 

결과

1) 출발도시: 1~N일때 모두 조사

2) 출발도시: 1일때 하나만 조사

 

요약

1. 문제를 증류하여 결국 원하는 목표가 무엇인지 파악하자. (이 문제의 경우 결국 순열을 찾는 문제이다.)
2. 순열은 dfs로 접근이 가능하다. 하지만, 접근 전에 Worst Case에 대해 시간초과가 나지않는지 파악하자.
3. dfs, bfs, backtracking등의 문제는 State Space Tree를 설계하고 접근하자.
4. Cycle을 찾는 문제는 Cycle이기 때문에 출발도시 하나에 대해서만 조사해도 된다.