[백준] 24512번 : Bottleneck Travelling Salesman Problem(Small) - 자바(JAVA)

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

24512번: Bottleneck Travelling Salesman Problem (Small)

 

문제 풀이 전 설계

from, to, cost를 가지는 Edge 클래스를 생성합니다.

한 정점에서 출발하여 N-1 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회이므로 최근에 배웠던 Prim 알고리즘과 Kruskal 알고리즘이 생각납니다.

 

하지만 다시 제자리로 돌아와야 하는점이 조금 다른 것 같고 N의 범위가 작기 때문에 완전 탐색도 가능해 보입니다.

c의 최대값은 5,000,000까지 가능하지만 간선의 개수가 많지 않기 때문에 int형을 사용해도 가능할 것 같습니다.

 

1. 두 정점 사이에 같은 방향의 간선이 2개 이상 존재하지 않는다.

2. 한 정점에서 출발해, 출발한 정점을 제외한 N-1개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다.

3. 정점 간 이동 비용의 최댓값이 최소화 하도록 방문해야 한다. 

이게 무슨말인가 싶었는데 이동 비용을 따로 고려해서 각각의 이동비용의 최댓값이 작도록 즉 각 이동 비용의 최댓값이 최소가 되도록 방문해야 합니다.

 

예를 들어 1 -> 3 -> 2 -> 1 을 하면

1 -> 3 cost = 2

3 -> 2 cost = 3

2 -> 1 cost = 5

이동비용의 최대값은 5입니다.

 

하지만 1 -> 2 -> 3 -> 1을 하면

1 -> 2 cost = 4

2 -> 3 cost = 4

3 -> 1 cost = 4

이동비용의 최대값은 4입니다.

 

따라서 이동비용의 최댓값이 최소가 되도록 해야 하므로 4가 정답입니다.

 

Greedy 한 접근법은  cost가 낮은 순으로 접근하면 반례가 있어서 불가능합니다.

 

또한 순회가 존재할 수도 존재하지 않을 수도 있습니다.

순회가 존재하더라도 1 -> 2 -> 3 과 1 -> 3 -> 2의 정답이 위의 예시처럼 다를 수 있습니다.

따라서 DFS로 완전탐색을 하면 괜찮을 것 같다라고 생각했습니다.

 

코드

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

public class Main_24512_BTSP {

	static int N;
	static int maxCost = Integer.MAX_VALUE;
	static int[][] graph;
	static int[] tempResult, result;
	static int start;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		graph = new int[N + 1][N + 1];
		result = new int[N];
		tempResult = new int[N];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			graph[from][to] = cost;
		}

		// 완전탐색

		for (int i = 1; i <= N; i++) {			
			visited[i] = true;
			tempResult[0] = i;
			start = i;
			DFS(i, 1, 0); 
			visited[i] = false;
		}

		if (maxCost == Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		StringBuilder sb = new StringBuilder();
		sb.append(maxCost + "\n");
		for(int i : result) {
			sb.append(i + " ");
		}
		System.out.println(sb);
	}

	private static void DFS(int currentVertex, int cnt, int tempCost) {
		
		// 한 사이클이 완성된다면
		if (cnt == N) {
			if(graph[currentVertex][start] == 0) {
				return;
			}
			tempCost = Math.max(tempCost, graph[currentVertex][start]);
			
			// 만약 모든 정점이 모두 방문되었다면 tempCost 갱신
			if (tempCost < maxCost) {
				maxCost = tempCost;
				result = tempResult.clone();
			}
			return;
		}

		for (int j = 1; j <= N; j++) {
			if (graph[currentVertex][j] == 0 || visited[j]) {
				continue;
			}

			visited[j] = true;
			tempResult[cnt] = j;
			DFS(j, cnt + 1, Math.max(tempCost, graph[currentVertex][j]));
			visited[j] = false;
		}
	}
}