[BOJ] 백준 10971 - 외판원 순회 2

1. 문제

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

10971번: 외판원 순회 2

2. 풀이

• 외판원(TSP)의 기본 문제 중 하나이다.
• 노드의 개수 <= 12면 BackTracking으로 해결 가능하나, 노드의 개수가 13 이상 16이하면 DP로 문제를 해결해야 한다.
• 이 문제의 경우 노드가 10개 이므로 BackTracking으로 해결이 가능하다.
• 시간 복잡도 -> $O(x^n)$

주요 자료구조
1. int[][] inMatrix : 인접 행렬
2. boolean[] nodeVisited : 노드 방문 처리 배열

 

• 입력으로 주어지는 값으로 인접 행렬을 구성한다.
• 이 문제의 포인트는 최소 값을 가지는 경로는 하나이기 때문에 모든 정점에서 DFS를 돌 필요 없이, 하나의 정점에서만 DFS를 돌면 최소 비용 경로가 보장된다.
• TspBackTracking() 함수를 돌면서 방문하지 않았고, 인접한 노드를 방문처리 하며 DFS를 돈다.
• 이때 재귀를 돌 때 isLoop()를 실행하여 모든 정점을 돌았는지 판단하고, 음의 가중치가 없기 때문에 마지막 노드에서 첫 번째 노드로 가는 길이 있을 때, 최소가 보장된다.
• 따라서 이때까지 더한 가중치의 최솟값을 result 변수에 갱신한다.
  
  
  

3.  소스 코드

import java.io.*;
import java.util.StringTokenizer;

/*
 *	노드의 개수 <= 12면 백트래킹 가능
 *  13 <= 노드의 개수 <= 16이면 DP로 해야함  
 *  시간 복잡도 O(x^n) :  x = 간선의 개수, n = 노드의 개수
 */

public class Main {
	static int N; // 도시 수
	static int[][] inMatrix; // 인접 행렬
	static boolean[] nodeVisited; // 노드 방문처리 배열
	
	static long result = Long.MAX_VALUE;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        
        // 인접행렬 구성
        inMatrix = new int[N][N];
        for (int i = 0; i < N; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	for (int j = 0; j < N; j++) {
        		inMatrix[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        // 어차피 최소 경로는 하나일 것이기 때문에 모든 정점에서 할 필요 없이 한 점에서만 하면 된다.
    	nodeVisited = new boolean[N];
    	nodeVisited[0] = true;
    	TspBackTracking(0, 0, 0);
        
        bw.write(Long.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 외판원 함수
	private static void TspBackTracking(int start, int idx, long val) {
		
		// 만약 모든 정점을 돌았고 마지막 정점에서 첫번째 정점까지 가는 길이 있을 때
		if (isLoop() && inMatrix[idx][start] != 0) {
			result = Long.min(result, val + inMatrix[idx][start]);
			return;
		}
		
		for (int i = 1; i < N; i++) {
			if (!nodeVisited[i] && inMatrix[idx][i] != 0) {
				nodeVisited[i] = true;
				TspBackTracking(start, i, val + inMatrix[idx][i]);
				nodeVisited[i] = false;
			}
		}
	}
	
	// 모든 정점을 돌았는지 확인하는 함수
	private static boolean isLoop() {
		for (int i = 0; i < N; i++) {
			if (!nodeVisited[i]) {
				return false;
			}
		}
		return true;
	}
}

4.  점수

80 / 100