[자바] 백준 23817 - 포항항 (boj java)

문제 : boj23817

 

  상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다.

 

  로직을 나눠서 생각해보자.

 

1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다.

-> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 있을 것이다. 그럼 그때부터는 최대 21개짜리 정점이 있는 그래프에서 최대 5개의 정점까지만 탐색해보는 완전탐색 문제라 생각할 수 있다.

 

2. '1'을 위해 모든 S와 K 사이의 거리를 알 필요가 있다. (정확힌 S에서 모든 K로 가는 거리와, 모든 K에서 모든 K로 가는 거리가 필요하다)

-> N과 M 사이즈를 보면 일단 floyd washall론 무리가 있다. 다익스트라를 쓰자니 어차피 배열에서 상하좌우 사이의 거리를 1로 한다면 모든 거리가 동일하니 그냥 bfs로 구하는게 더 빠르다. 그러니 모든 S와 K에서 출발하는 bfs를 통해 모든 정점 사이의 거리를 알아두면 된다.

 

그럼 이제 '1'을 구할 수 있다! 정리하자면

A. bfs로 모든 정점 사이의 거리 확인하고, 최대 21개의 정점이 있는 그래프 형태로 변경

B. 그럼 그래프에서 최대 5개까지만 가면 되는 완전 탐색 문제로 변경되므로 그냥 20P5개의 경우의 수 중 최소 시간을 구해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    int n, m;
    int answer = Integer.MAX_VALUE;
    int[][] arr;
    int[][] dist = new int[22][22];
    boolean[] dfsV = new boolean[22];

    private void dfs(int a, int cnt, int distSum) {
        if (cnt == 5) {
            if (answer > distSum) answer = distSum;
            return;
        }
        for (int i = 2; i < 22; i++) {
            if (dist[a][i] == 0 || dfsV[i]) continue;
            dfsV[i] = true;
            dfs(i, cnt+1, distSum+dist[a][i]);
            dfsV[i] = false;
        }
    }
    private void bfs(int r, int c) {
        boolean[][] v = new boolean[n][m];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{r, c, 0});
        v[r][c] = true;
        while (!q.isEmpty()) {
            int cr = q.peek()[0];
            int cc = q.peek()[1];
            int cd = q.peek()[2];
            q.poll();
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (((dr^dc)&1) != 1) continue;
                    int nr = cr+dr;
                    int nc = cc+dc;
                    if (nr<0||nr>=n||nc<0||nc>=m||v[nr][nc]||arr[nr][nc]<0) continue;
                    v[nr][nc] = true;
                    if (arr[nr][nc] > 0) {
                        dist[arr[r][c]][arr[nr][nc]] = cd+1;
                    }
                    q.add(new int[]{nr, nc, cd+1});
                }
            }
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        int num = 2;
        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                switch (row.charAt(j)) {
                    case 'S': arr[i][j] = 1; break;
                    case 'K': arr[i][j] = num++; break;
                    case 'X': arr[i][j] = -1; break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] >= 1)
                    bfs(i, j);
            }
        }
        dfs(1, 0, 0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}