[백준 / Java] 17182번: 우주 탐사선 (골드3)

문제 풀이 날짜: 2023.10.11
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 17182번: 우주 탐사선 (골드3)

 

키워드

플로이드-워샬, DFS

 

풀이 접근법

• 입력 그래프가 인접 행렬로 주어지며, 모든 행성을 탐사하기 위한 최소 시간이 필요하므로 플로이드-워샬로 풀이한다.
• 그런데 여기서 플로이드 워샬로 구해진 결과물은 단순히 각 점으로 가는 최소 시간(최단 경로)일 뿐이다. 우리가 구하고 싶은 것은 시작점부터 모든 정점을 지나는 최소 시간이다.
• 따라서 0부터 모든 정점을 지나는 경로는 DFS(그래프 탐색)로 구해준다. (N은 최대 10)
• 시작점 K는 문제에서 주어진다. 중복 경우를 제거하기 위해 시작점을 visit하고 depth 1부터 시작한다.
  • Why? : 어떤 시작점 A에서 출발해서 B, C, D를 방문한다고 가정할 때, A부터 방문해야 하는 것은 이미 자명한 사실임.
  • ⇒ 시작점을 제외한 (N-1)! 가지 경우의 수만 구하면 된다.
  • 또, A에서 출발하여 B에 도착하는 경우를 찾고싶을 때 A-B-(C-D) 라는 경우까지 구해버리면 유의미한 경우의 수가 아님.

 

코드

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

public class Main {

	private static int N;
	private static int K;
	
	private static final int INF = 9_999_999;
	
	private static boolean[] visited;
	private static int[][] D;
	
	private static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		
		N = Integer.parseInt(temp[0]);
		K = Integer.parseInt(temp[1]);
		
		visited = new boolean[N];
		D = new int[N][N];
		
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				D[i][j] = Integer.parseInt(st.nextToken());
			}
		}
				
		//플로이드 워샬
		for(int k = 0; k < N; k++) { //경
			for(int i = 0; i < N; i++) { //출
				for(int j = 0; j < N; j++) { //도
					D[i][j] = Math.min(D[i][k] + D[k][j], D[i][j]);
				}
			}
		}
		
		visited[K] = true; //시작점을 체크하고 진입한다.
		DFS(1, K, 0); //주의: depth가 1부터 시작
		
		System.out.println(min);
	}

	private static void DFS(int depth, int start, int dist) {
		if(depth == N) {
			min = Math.min(dist, min);
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(i == start) { continue; }
			
			if(!visited[i]) {
				visited[i] = true;
				DFS(depth + 1, i, dist + D[start][i]);
				visited[i] = false;
			}
		}
	}
}

---

 

 

참고한 링크

https://bleron.tistory.com/215
https://dlwnsdud205.tistory.com/253