17182번 - 우주 탐사선

2025-01-01

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 풀이:

처음에는 그냥 플로이드로 모든 경로의 최단 거리를 구하고

각 위치에서 가지 않은 행성 중 최단 거리인 행성을 골라서 가는 방식으로 문제를 풀었다.

플로이드 함수

Java

public static void update() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i==j)
                    continue;
                for (int k = 0; k < n; k++) {
                    arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
    }

최단 거리 계산

Java

Queue<Integer> q = new LinkedList<>();
visited[k] = true;
q.add(k);

int sum = 0;

while (!q.isEmpty()) {
	int a = q.poll();
	int min = Integer.MAX_VALUE;
	int idx = a;

	for (int i = 0; i < n; i++) { //현재 행성에서 갈 수 있는 모든 행성 탐색
		if (visited[i]||a==i) { //방문했거나 현재 행성과 같다면 패스
			continue;
		}
		if (min > arr[a][i]) { //이동 시간이 더 짧다면 교체
			min = arr[a][i];
			idx = i;
		}
	}

	if (idx != a) { //현재 행성과 저장된 행성이 같다면 모든 행성을 방문했다는 뜻
	sum += min;
	visited[idx] = true;
	q.add(idx);
	}
}

근데 이건 아주 잘못된 접근이었다.

제대로된 풀이를 하려면 시작지점에서부터 모든 경우를 계산하면 되는 것이다.

실제로 모든 경우의 수를 다 해보더라도 행성의 개수가 10개이므로 크게 부담되지 않는다.

그래서 위의 코드에서 최단 거리 계산 코드를 아래와 같은 코드로 바꿔주면 된다.

Java

public static void calc(int cnt, int a, int sum) { //행성 방문 개수, 현재 행성, 거리 합계
    if (ans < sum) { //이미 최단값보다 크다면 할필요 없음
        return;
    }
    if (cnt >= n) { //모든 행성을 방문했다면 최단값 업데이트
        ans = sum;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (visited[i] || a == i) {
            continue;
        }
        visited[i] = true; 
        calc(cnt + 1, i, sum + arr[a][i]); //재귀
        visited[i] = false;
    }
}

전체 코드

Java

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

public class Main {
    public static int n,k;
    public static int ans = Integer.MAX_VALUE;
    public static int[][] arr;
    public static boolean[] visited;

    public static void calc(int cnt, int a, int sum) {
        if (ans < sum) {
            return;
        }
        if (cnt >= n) {
            ans = sum;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i] || a == i) {
                continue;
            }
            visited[i] = true;
            calc(cnt + 1, i, sum + arr[a][i]);
            visited[i] = false;
        }
    }

    public static void update() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i==j)
                    continue;
                for (int k = 0; k < n; k++) {
                    arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
    }

    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());
        arr = new int[n][n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        update();

        visited[k] = true;
        calc(1, k, 0);
        System.out.println(ans);
    }
}