- 오늘의 학습 키워드 : 플로이드-워샬, 백트래킹
[문제 이름 : 우주 탐사선 (백준 17182, G3)]
문제 url : https://www.acmicpc.net/problem/17182
내가 작성한 코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main {
static int[][] dist;
static int N, K, ans = Integer.MAX_VALUE;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
dist = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
dist[i][j] = Integer.parseInt(st.nextToken());
}
}
// 방문한 점을 중복 방문할 수 있기에, '모든 점에서 최단 거리'를 구하고 경우의 수를 따져봐야 한다.
// => 플로이드 워셜 알고리즘 사용
for (int k = 0; k < N; k++) {
for (int j = 0; j < N; j++) {
for (int i = 0; i < N; i++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
visited = new boolean[N];
visited[K] = true;
backTrack(1, K, 0);
System.out.println(ans);
}
static void backTrack(int cnt, int prev, int d) {
if (cnt == N) {
ans = Math.min(ans, d);
}
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
visited[i] = true;
backTrack(cnt+1, i, d + dist[prev][i]);
visited[i] = false;
}
}
}
풀이 과정 (풀이 시간 : 1시간)
탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.
이 문장의 조건을 해석한다면 다음과 같이 풀이할 수 있다.
// 방문한 점을 중복 방문할 수 있기에, '모든 점에서 최단 거리'를 구하고 경우의 수를 따져봐야 한다.
// => 플로이드 워셜 알고리즘 사용
플로이드-워셜 알고리즘을 사용해서 모든 점에서 최단 거리를 구한 다음, 백트래킹을 이용해서 모든 정점을 다 탐색한 경우 최솟값 ans를 갱신해간다.
1. 입력 처리:
(1) 행성의 개수 N과 탐사를 시작할 행성의 위치 K를 입력받는다.
(2) dist라는 2차원 배열에 각 행성 간의 이동 시간을 저장한다.
2. 플로이드-워셜 알고리즘:
(1) 이 부분은 dist 배열을 모든 점에서 모든 점까지의 최단 거리로 변환한다.
(2) 3중 반복문을 사용하여 dist[i][j]에 대해 모든 중간 경로 k를 고려해 최단 경로를 갱신한다.
(3) 결과적으로 dist[i][j]는 행성 i에서 j로 이동하는 최단 시간이 된다.
3.백트래킹을 이용한 모든 경로 탐색 (backTrack 함수):
(1) backTrack 함수는 재귀적으로 백트래킹을 수행하며 가능한 모든 탐사 경로를 탐색한다.
(2) cnt는 현재 방문한 행성의 수를 나타내며, prev는 이전에 방문한 행성을 나타낸다.
(3) d는 현재까지의 이동 거리를 의미한다.
(4) 모든 행성을 방문하면 ans를 최소값으로 갱신한다.
4. 방문한 행성을 추적하는 visited 배열:
(1) 각 재귀 호출에서 현재 행성을 방문 상태로 표시하고, 탐색이 끝난 후 다시 방문하지 않은 상태로 돌린다(백트래킹).
(2) 모든 경우의 수를 탐색하므로, 모든 행성을 방문하는 경로 중 최소 거리를 구할 수 있다.
내일은 웹 프론트 강의를 인프런에서 수강할 예정이다.