[BOJ] - 외판원 순회 2 / 10971번 (Java)

[BOJ] - 외판원 순회 2 / 10971번 (Java)

[BOJ] - 외판원 순회 2 / 10971번 (Java)

1. 문제 접근

기존의 외판원 순회 문제에서 최종 목적지에서 출발지로 다시 돌아와야하는 변형된 외판원 순회 문제다.

 

또한, 각 도시마다 경로가 있을 수도 있고, 없을 수도 있다.

 

도시의 개수(N)이 최대 10개 밖에 되지 않으므로, 모든 도시를 줄세우는 방식의 순열을 사용하여 완전 탐색을 할 수 있다.

 

하지만 이전 도시와 다음 도시 간에 간선이 있는지 없는지에 따라 백트래킹을 진행하였다.

int beforeNode = selectList[selectIdx - 1];
int currNode = elementList[idx];
// 경로가 없는 경우 pruning
if (adMatrix[beforeNode][currNode] == 0) {
    continue;
}

 

또한 추가적으로 현재 제작중인 순열에 대해 누적 비용을 함께 매개변수로 넘겨 이미 최소비용을 넘겼다면 가지치기(pruning)을 진행하여 최적화를 진행했다.

// 이미 최소 비용을 넘었다면 pruning
if (costSum > minCost)
    return;

 

이후 기저조건에 도달하였다면, 최소 비용을 갱신할 수 있는 유망성이 있는 순열이므로, 도착지와 출발지의 경로가 있는지 확인하고 있다면 비용을 더한다.

if (selectIdx == N) {
    int srcNode = selectList[N-1];
    int destNode = selectList[0];
    // 최종 목적지에서 다시 출발점으로 돌아오는 비용 계산
    if (adMatrix[srcNode][destNode] == 0) {
        // 경로가 없는 경우
        return;
    }
    costSum += adMatrix[srcNode][destNode];
    minCost = Math.min(minCost, costSum);
    return;
}

 

이후, 최소비용과 비교하여 최소 비용보다 작다면 갱신해나간다.

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * [BOJ] - 외판원 순회 2 / 10971번 
 * @author JinHxxxxKim
 * 
 * 1. 도시를 방문한 순서를 정한다(순열)
 * 2. 현재의 비용을 함께 매개변수로 전달하여 백트래킹
 * 		- 주어진 순열에 대해 인접행렬을 이용해 비용을 구한다. (0이라면 백트래킹)
 * 3. 경로가 없다면 다음 노드를 조회
 * 4. 기저조건(모든 도시를 다 골랐을 경우)
 * 		- 마지막으로 도착지에서 출발지로 다시 돌아오는 경로의 비용을 구한다.
 * 			- 0일 경우 불가능한 경로 이므로 바로 return
 * 		- 비용을 모두 구했다면 최소비용과 비교하여 갱신한다.
 * 
 */
public class Sol_10971 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;

	static int N;
	static int[][] adMatrix;
	static int minCost;

	static int[] elementList;
	static boolean[] isSelected;
	static int[] selectList;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine().trim());
		adMatrix = new int[N][N];
		for (int row = 0; row < N; ++row) {
			st = new StringTokenizer(br.readLine().trim());
			for (int col = 0; col < N; ++col) {
				adMatrix[row][col] = Integer.parseInt(st.nextToken());
			}
		}

		elementList = new int[N];
		isSelected = new boolean[N];
		selectList = new int[N];
		for (int num = 0; num < N; ++num)
			elementList[num] = num;

		minCost = Integer.MAX_VALUE;
		makeDestSeq(0, 0);
		System.out.println(minCost);
	}

	/**
	 * 목적지 순서를 정하고 비용을 구하는 메소드
	 * @param selectIdx 선택할 요소의 인덱스
	 * @param costSum 현재까지의 누적 비용
	 */
	private static void makeDestSeq(int selectIdx, int costSum) {
		// 이미 최소 비용을 넘었다면 pruning
		if (costSum > minCost)
			return;
		// 기저조건
		if (selectIdx == N) {
			int srcNode = selectList[N-1];
			int destNode = selectList[0];
			// 최종 목적지에서 다시 출발점으로 돌아오는 비용 계산
			if (adMatrix[srcNode][destNode] == 0) {
				// 경로가 없는 경우
				return;
			}
			costSum += adMatrix[srcNode][destNode];
			minCost = Math.min(minCost, costSum);
			return;
		}

		for (int idx = 0; idx < N; ++idx) {
			if (isSelected[idx])
				continue;
			
			// 처음 도시를 선택할 경우는 pruning X
			if (selectIdx == 0) {
				// 전처리
				isSelected[idx] = true;
				selectList[selectIdx] = idx;
				makeDestSeq(selectIdx + 1, costSum);
				// 후처리
				isSelected[idx] = false;
			} else {
				int beforeNode = selectList[selectIdx - 1];
				int currNode = elementList[idx];
				// 경로가 없는 경우 pruning
				if (adMatrix[beforeNode][currNode] == 0) {
					continue;
				}
				// 전처리
				isSelected[idx] = true;
				selectList[selectIdx] = idx;
				makeDestSeq(selectIdx + 1, costSum + adMatrix[beforeNode][currNode]);
				// 후처리
				isSelected[idx] = false;
			}
		}
	}
}

---

3. 디버깅

처음 풀 때는 가지치기를 하지 않고, 모든 순열을 만든다음에 비용을 계산하는 방식으로 진행했다.

 

300ms로 문제 통과는 했지만, 100ms로 문제를 통과하는 경우가 있는 것을 확인하고, 누적 비용을 통한 최적화를 했고, 104ms 까지 최적화할 수 있었다.

 

---

4. 결과