백준 17182 JAVA

문제 유형

• 플로이드-위셜 알고리즘

문제 접근

• 답
  • 모든 행성 방문 최소 시간
• 주어지는 정보
  • 맵 크기 최대 100 (N*N)
  • 행성 시작 지점(K)
• 후보
  • 완전 탐색
    • 실패
    • 방문한 곳을 재방문 가능함. 따라서, 각 경우의 수마다 방문한 곳을 재방문 하면 무한 반복 발생
• 해결 방법
  • 플로이드-와샬 알고리즘
    • 모든 정점에서 다른 정점으로의 최단 거리 갱신

int[][] graph;

static void floyd(int[][] graph){
    for(int k = 0; k<N; k++){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

 

시간 계산

• 플로이드
  • 101010 = 1000
• 플로이드로 구한 그래프에서 재귀 탐색
  • (10-1)! = 362880
• 총합
  • 363880 ⇒ 통과

 

코드

import java.io.*;
import java.util.*;


class Main {
    static int N, K;
    static int[][] map;
    static int[][] graph;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;


    static void floyd(){
        int MAX = 9999999;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                graph[i][j] = map[i][j];
            }
        }

        for(int k = 0; k<N; k++){
            for(int i = 0; i<N; i++){
                for(int j = 0; j<N; j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

    static void dfs(int total, int cur, int cnt){
        if(cnt == N){
            answer = Math.min(answer, total);
        }

        for(int i = 0; i<N; i++){
            if(visited[i] == true){
                continue;
            }

            visited[i] = true;
            dfs(total + graph[cur][i], i, cnt + 1);
            visited[i] = false;
        }
    }

    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());
        
        map = new int[N][N];
        graph = new int[N][N];
        visited = new boolean[N];
        visited[K] = true;

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

        floyd();
        dfs(0,K,1);
        

        System.out.println(answer);
    }
}