[백준] 2089번 : 외판원순회 - 자바(JAVA)

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

2098번: 외판원 순회

 

문제 해석

N개의 도시가 존재합니다.

도시를 연결하는 단방향 도로가 존재하며 도로를 가는 데는 비용이 존재합니다.

 

문제 풀이 전 설계

1번도시에서 출발한 경우, 2번 도시에서 출발한 경우를 모두 DFS를 통해 완전 탐색해보기 -> 시간 초과

 

 

문제 풀이하면서

1번 도시에서 출발한 경우, 2번 도시에서 출발한 경우를 세어줄 필요는 없습니다.

어떤 도시를 선택해도 다시 출발 도시로 돌아오는데 드는 최소 비용은 같습니다.

다시 출발 도시로 돌아오기 때문에 사이클이 발생하기 때문입니다.

1 -> 2 -> 3

2 -> 3 -> 1

3 -> 1 -> 2

 

하지만 출발 도시를 1개로 선정해도 역시나 시간 초과입니다.

 

경로를 줄여야 하므로 Greedy 또는 DP로 저장하면서 시간을 줄여나가야 할 것 같다.

 

외판원 순회 DP + 비트 마스킹 + DFS로 해결할 수 있습니다.

https://junuuu.tistory.com/214?category=987844 

외판원 순회(TSP : Traveling Salesperson Problem) 알고리즘

 

완전 탐색 코드 - 6% 시간 초과

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

public class Main_2089_외판원순회 {

	static int N, firstNode;
	static int result = Integer.MAX_VALUE;
	static int[][] city;
	static boolean[] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		city = new int[N][N];

		StringTokenizer st = null;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				city[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 입력 끝

		// 완전탐색

		int sum = 0;
		visited = new boolean[N];
		firstNode = 0;
		search(firstNode, sum);
		System.out.println(result);

	}

	private static void search(int startNode, int sum) {

		for (int i = 0; i < N; i++) {
			if (i == startNode) {
				continue;
			}

			if (visited[i]) {
				continue;
			}
			// System.out.println("start Node : " + startNode + "to Node : " + i);

			if (city[startNode][i] != 0) {
				sum += city[startNode][i];
				

				visited[i] = true;

				// 시작점으로 다시 돌아왔다면
				if (i == firstNode) {
					if (!isAllTrabled()) {
						visited[i] = false;
						sum -= city[startNode][i];
						continue;
					}
					// 모두 순회를 했다면
					result = Math.min(result, sum);
				}

				search(i, sum);
				sum -= city[startNode][i];
				visited[i] = false;
			}
		}
	}

	private static boolean isAllTrabled() {
		for (boolean e : visited) {
			// 방문되지 않은 정점들이 있으면 false
			if (!e) {
				return false;
			}

		}
		return true;
	}

}

 

외판원 순회 DP+비트 마스킹+ DFS 코드

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

// 외판원 순회
// 다이나믹 프로그래밍
public class Main_2089_외판원순회DP {
	static int n;
	static int[][] map;
	static int[][] dp;
	static final int INF = 11_000_000; // MAX : 11,000,000
	//Integer.MAX_VALUE를 쓰지 않은 이유는 이후에  return을 하면서 값을 더해서 비교하는 부분이 있을때
	//overFlow가 발생하는 경우가 있었음.

	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		// i : 현재 위치한 도시, j : 지금까지 방문한 도시 2진수
		dp = new int[n][(1 << n)]; // ex) 1 << 5 = 100000(2) = 32 -> 우리의 최대값 : 11111(2) 이므로 1 빼기

		// 1) Map 입력받아 대입하기
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int weight = Integer.parseInt(st.nextToken());
				map[i][j] = weight;
			}
		}

		// dp배열 초기화
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], INF);
		}

		System.out.println(dfs(0, 1));
	}

	// 어느 도시에서 시작하든지 최소비용은 같기 때문에 편안하게 0번도시부터 시작하자
	// @param: city - 현재 위치한 도시 인덱스, visitBitMask - 지금까지 방문한 도시 2진수
	// DFS 알고리즘
	private static int dfs(int city, int visitBitmask) {

		if (visitBitmask == (1 << n) - 1) { // 모든 도시를 방문했다면

			// 현재 경로에서 0으로 도달할 수 없다면
			if (map[city][0] == 0) {
				return INF;
			}

			return map[city][0]; // 현재 도시 -> 0번쨰(시작) 도시 이동 거리
		}

		if (dp[city][visitBitmask] != INF) { // dp값이 존재하는경우
			return dp[city][visitBitmask];
		}

		// 현재 도시(city)에서 각 i의 도시로 이동한 경우에 대해 DFS 수행
		for (int i = 0; i < n; i++) {
			// 한 번이라도 그 도시를 방문했는데 다시 그 도시를 방문하는 경우 예외처리
			if ((visitBitmask & (1 << i)) > 0 || map[city][i] == 0) {
				continue;
			}

			// d[i][j] = 현재 있는 도시가 i이고 이미 방문한 도시들의 집합이 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로
			// 돌아올 때 드는 최소 비용.
			// 즉, 방문해야하는 도시(여기에 시작지점으로 돌아오는 것 포함) 들까지 가는 최소 비용
			dp[city][visitBitmask] = Math.min(dp[city][visitBitmask], dfs(i, visitBitmask | (1 << i)) + map[city][i]);
			// dfs(다음 도시, 다음도시 방문했다고 가정) + 여기서 다음 도시까지의 거리 와 최소거리 비교
		}

		return dp[city][visitBitmask];
	}
}