[Java] 백준 2098번 : 외판원 순회*

1. 문제

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

2098번: 외판원 순회

 

 

 

2. 풀이 과정

재귀 + 2차원 배열 DP문제라고 할 수 있다.

처음엔 순열을 돌려서 전체 탐색을 했는데 경우의 수가 16!으로 결국 시간 초과가 발생했다.

해결 방안이 떠오르지 않아, 질문을 보고 힌트를 얻어 풀 수 있었다.

 

 

이 문제의 key point는 2가지다.

1) 루프는 시작점이 어디든, 더해지는 값이 같기 때문에 값의 총합은 같다. => 시작점은 0으로 해서 for문을 1부터 돌림

2) 현재 => 다음 + 다음 => 아직 방문하지 않은 것들을 방문하는 최소값

 

2)의 내용을 예를 들어 보면, 노드가 0, 1, 2, 3, 4 가 있다고 하자.

갈 수 있는 경로 중, 0 => 1 => 2 + (3, 4) 와 0 => 2 => 1 + (3, 4)로 중복되는 연산이 있어 재사용한다.

여기서 (3, 4)는 아직 방문 안 한 곳들로 min(3=>4=>0, 4=>3=>0)이 반환된다.

 

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

public class Boj2098 {
	static int N, arr[][], memo[][];
	static final int INF = 999_999_999;
	
	public static int go(int now, int visited) {
		//다 방문했다면
		if(visited == (1<<N)-1) { return arr[now][0];}//출발지로 돌아가는 값
		
		//이미 계산이 끝난 값이라면
		if(memo[now][visited]!=0) { return memo[now][visited];}
		
		memo[now][visited]=INF;
		for(int i=1; i<N; i++) {//다음 갈 곳 선택 = 출발지가 0임을 아니까 1부터 시작
			if((visited & (1<<i)) != 0) { continue;} //이미 방문했으면
			if(arr[now][i]==0) { continue;}//연결된 길이 없으면
			memo[now][visited] = Math.min(memo[now][visited], arr[now][i]+go(i, visited | (1<<i)));
		}
		return memo[now][visited];
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		memo = new int[N][1<<N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j]==0) {arr[i][j]=INF;}
			}
		}
		System.out.println(go(0, 1<<0)); //0부터 시작
	}
}