99클럽 코테 스터디 21일차 TIL (챌린저): [백준][Java] 17182 우주 탐사선 - 골드3

 

문제 보기

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

 

 

풀이

이전 노드에 다시 방문할 수 있다는 점이 조금 어려웠다.

그냥 탐색하지 않은 노드만 방문해도 된다면 쉬웠을텐데 말이다.

 

그래서 "탐색하지 않은 노드만 방문"해도 되게 하는 법을 생각했다.

각 노드에서 다른 노드들로의 최단거리를 미리 구해 놓는 것이다.

예시의 이 그래프를 보며 각 노드에서 최단 거리를 유도해보자.

답은 이렇게 될 것이다.

 

그럼 이제 새로 구한 최단거리 그래프를 바탕으로 모든 경로를 탐색해보고 min 값을 구해볼 수 있겠다.

 

  private static void dfs(int start, int cur, int[][] arr, int[][] dist) {
    for(int i = 0; i < N; i++) {
      if(dist[start][i] > dist[start][cur] + arr[cur][i]) {
        dist[start][i] = dist[start][cur] + arr[cur][i];
        dfs(start, i, arr, dist);
      }
    }
  }

  private static void dfs2(int cur, int[][] arr, boolean[] visited, int depth, int dist) {
    if(depth == N) {
      min = Math.min(min, dist);
    }
    for(int i = 0; i < N; i++) {
      if(!visited[i]) {
        visited[i] = true;
        dfs2(i, arr, visited, depth + 1, dist + arr[cur][i]);
        visited[i] = false;
      }
    }
  }

순서대로 다익스트라, 백트래킹 알고리즘을 적용한 dfs이다.

위 dfs가 최단거리 그래프를 구하는 역할을 하고,

아래 dfs가 문제의 답을 구하는 역할을 한다.

 

 

전체 코드

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

public class Main {
  private static int min = Integer.MAX_VALUE;
  private static int N;
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    int[][] arr = new int[N][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());
      }
    }
    int[][] dist = new int[N][N];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        dist[i][j] = Integer.MAX_VALUE;
      }
    }
    for(int i = 0; i < N; i++) {
      dist[i][i] = 0;
      dfs(i, i, arr, dist);
    }

    boolean[] visited = new boolean[N];
    visited[K] = true;
    dfs2(K, dist, visited, 1, 0);

    bw.write(min + "\n");

    bw.flush();
    bw.close();
  }

  private static void dfs(int start, int cur, int[][] arr, int[][] dist) {
    for(int i = 0; i < N; i++) {
      if(dist[start][i] > dist[start][cur] + arr[cur][i]) {
        dist[start][i] = dist[start][cur] + arr[cur][i];
        dfs(start, i, arr, dist);
      }
    }
  }

  private static void dfs2(int cur, int[][] arr, boolean[] visited, int depth, int dist) {
    if(depth == N) {
      min = Math.min(min, dist);
    }
    for(int i = 0; i < N; i++) {
      if(!visited[i]) {
        visited[i] = true;
        dfs2(i, arr, visited, depth + 1, dist + arr[cur][i]);
        visited[i] = false;
      }
    }
  }

}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/17182.%E2%80%85%EC%9A%B0%EC%A3%BC%E2%80%85%ED%83%90%EC%82%AC%EC%84%A0

CodingTest_AutoSave/백준/Gold/17182. 우주 탐사선 at main · MetroDefro/CodingTest_AutoSave