[백준 2098] 외판원 순회 풀이 -JAVA

외판원 순회 풀이 - JAVA

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

2098번: 외판원 순회

문제 설명

• TSP 라고 외판원 순회라는 유명한 문제이다
• N 개의 도시가 있고, 외판원은 도시를 순회한다
• 방문한 마을을 다시 방문할 수 없고 모든 도시를 방문하고 시작도시로 돌아와야한다
• 순회시 최단 코스트를 구하라

문제풀이

• 시작지점을 고정한다
  • 시작마을은 고정해도 된다 어짜피 순회 할 것이기 때문이다
  • A -> B -> C -> A  순으로 이동한다치면  어느지점에서 시작하든 코스는 같기 때문이다
• bit 마스크를 활용한다
  • 쓰는 이유는 방문한 도시는 재방문 못하기때문
  • 따라서 한번씩만 도시에 방문해야하는데 bit 마스크방법이 경제적이기때문
  • 0001 : 1번마을 방문
  • 0011 : 1,2 번 마을 방문
  • 0111 : 1,2,3 번 마을 방문
  • 총 16자리만 사용하면 되고 int 범위안에있다
• DFS를 돌린다
  • 기존 DFS방식과 동일하다 다만 간선정보는 bit마스크활용해서 0인 미방문도시에 DFS를 재귀돌린다
  • 단 이때 갈수없는 도시면 제외한다
• 여기까지하면 완전 탐색이 가능하다
• 가지치기한다
  • 메모이제이션을 활용한다
  • int[도시][비트마스크] 형태로 이미 계산한 cost 정보는 재활용한다
  • vis[cur][visit] = Math.min(vis[cur][visit], dfs(i, (visit | next)) + graph[cur][i]);
  • vis[도시][bit] = Math.min(vis[도시][bit]  ,  다음도시 방문 DFS cost 합)
  • vis[도시][비트마스크]에 값이 들어가는 경우를 따져봐야 이 방법이 이해가된다.
  • 처음에 -1값으로 모두 초기화된 후에 값이 들어가는 경우는
    DFS Tree의 최하 leaf 들에서 return 이 최초발생하며 값이 들어가게된다
  • 예를들어 A,B,C,D,E 마을까지 있다
  • 현재 C마을이고 00111 상태이다
  • vis[C][00111] 의 값이 저장되는 것은 Min (ABC - D - E , ABC - E - D) 가 될 것이다
  • vis[C][00111] = D,E 방문에 대한 Cost 합 Min 값이다, 앞의 ABC 방문과 상관이 없다
  • 트리의 제일 끝 leaf 들부터 공략해가면서 재연산을 막는 개념이다
• 주의할 점
  • DFS 연산을 그림으로 그려보면 Tree가나온다
    • 방문여부까지 체크해주면 스패닝트리가나온다
  • Return은 끝  Leaf에서 부터 순차적으로 발생한다
  • 끝 Leaf 부터 DP로 활용할만한 Data가 쌓여서 Root까지 오는 것이다
  • 외판원 순회는 DFS 테크닉 문제인 것이다
  • 메모이제이션 할때 최초값은 -1을 넣던 무한대를 넣던 상관없지만
    시작마을로 못가서 INF 리턴되는 것과는 구분해야한다
    왜냐하면 구분하지않으면 가지치기가 덜 된다. (이거 주의)

 

코드

package graph_theory.B2098;

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

/**
 * https://www.acmicpc.net/problem/2098
 * title : 외판원 순회
 * @author tempcru
 * 
 * 유명한 문제, 비트마스킹과 DFS의 조화
 */
public class Main {

	static int N; // [2, 16]
	static int[][] graph; // Cost Matrix 
	static int allVisited;
	private static int[][] vis; // 방문여부
	
	private static final int INF = (int) (1e9); // 무한대 값 처리
	
	public static void main(String[] args) throws Exception {

		//System.setIn(new FileInputStream("./src/graph_theory/B2098/sample_data"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		

		// 1. Read 도시의 수
		N = Integer.parseInt(br.readLine().trim());
		allVisited = (1 << N) - 1;
		
		// 2. 도시 Cost Matrix
		graph = new int[N][N];
		vis = new int[16][allVisited]; // int[도시][비트마스크]
		

		// 3. Read 도시 Cost
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < N; i++) {
			Arrays.fill(vis[i], -1);
        }
		
		// 0, 0000 0000 0000 0001 
		// 0번째 마을에서 시작하고 0번째 마을
		System.out.println(dfs(0, 1));
	}
	
	public static int dfs(int cur, int visit) {
			
			if (visit == allVisited) {
				//모든마을 방문하고 시작 마을로 방문할 수 없다면 0
				//갈 수 있다면 graph[cur][0] 리턴
	            return graph[cur][0] == 0 ? INF : graph[cur][0];
	        }
		
			//이미 방문했다면 return, 중복제거
			//INF와 비교하면안됨 이유는 visit == allVisited 에서 return INF가 가능하기 때문임
			//그렇다면 vis[cur][visit] 값이 INF인데 해당 값은 이미 계산 한 경우이기 때문에
			//구지 연산할 필요없이 INF 값으로 다시 return 해야하는 것임 그래서 -1과 비교해야함
			if (vis[cur][visit] != -1) {
	            return vis[cur][visit];
	        }
			
			vis[cur][visit] = INF; //방문처리
			
			int next;
			for(int i = 0; i < N; i++) {// DFS 돌리기
				
				// 1번도시 : 0000 0000 0000 0001
				// 2번도시 : 0000 0000 0000 0010
				next = 1 << i;
				if (graph[cur][i] != 0  //갈수 있는 도시고
				&& ((visit & next) == 0)) { // 방문하지않았다면 
					vis[cur][visit] = Math.min(vis[cur][visit], dfs(i, (visit | next)) + graph[cur][i]);
				}
			}
			
			return vis[cur][visit];
		}

}