[백준] 23817 포항항

1. 문제

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

23817번: 포항항

2. 접근방법

ꉂꉂ(ᵔᗜᵔ*) 포항항 귀엽

 

뭔가 그리디한 방법이 있나 싶지만

보통 이런식으로 여러 곳을 들리는데 최적의 값을 구하는 것은 보통 브루트포스다.

 

이 문제도 마찬가지로 최대 20곳 중에서 5곳을 들리는 (20P5) 순열로 모든 경우의 수를 구해서 그 중 최적인 값을 구하면 된다.

 

대신 각각 노드끼리의 최소거리 역시 직접 구해야하는데

이 때 bfs를 사용해서 각 식당 마다 맵 전체 탐색하며 다른 식당들과의 거리를 구해두면 된다.

 

3. 자바 코드

package backjoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class P23817포항항 {

    static String map[];
    static HashMap<Character, HashMap<Character, Integer>> distStorage;
    static int N,M,answer;
    static char order;

    public static void main(String[] args) 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());
        map = new String[N];
        order = 'a';
        for (int i = 0; i < N; i++) {
            char [] charArray = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (charArray[j] == 'K') {
                    charArray[j] = order;
                    order = (char) (order + 1);
                }
            }
            map[i] = new String(charArray);
        }
        if (order - 'a' < 5) {
            System.out.println(-1);
            return;
        }
        answer = Integer.MAX_VALUE;
        makeDistStorage();
        perm(0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);

    }
    public static void makeDistStorage(){
        distStorage = new HashMap<>();
        int dr[] = new int[]{0, 0, 1, -1};
        int dc[] = new int[]{1, -1, 0, 0};

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i].charAt(j) != 'X' && map[i].charAt(j) != '.') {
                    boolean[][] visit = new boolean[N][M];
                    Queue<Point> que = new LinkedList<>();
                    que.add(new Point(i, j));
                    int dist = 0;
                    char root = map[i].charAt(j);
                    HashMap<Character, Integer> hashMap = new HashMap<>();
                    while (!que.isEmpty()) {
                        int size = que.size();
                        dist++;
                        while (size-- > 0) {
                            Point now = que.poll();
                            for (int r = 0; r < 4; r++) {
                                int row = now.x + dr[r];
                                int col = now.y + dc[r];
                                if (row < 0 || col < 0 || row >= N || col >= M) continue;
                                if (visit[row][col]) continue;
                                if (map[row].charAt(col) == 'X') continue;
                                if (map[row].charAt(col) != '.') {
                                    hashMap.put(map[row].charAt(col), dist);
                                }
                                que.add(new Point(row, col));
                                visit[row][col] = true;
                            }
                        }

                    }
                    distStorage.put(root,hashMap);
                }
            }
        }
    }
    static char [] sel = new char[5];
    static boolean visit [] = new boolean[1000];
    public static void perm(int idx){
        if(idx == 5){
            int nowDist = check();
            if(nowDist == -1) return;
            answer = Math.min(answer,nowDist);
            return;
        }
        for(char c = 'a'; c < order ; c++){
            if(!visit[c]){
                sel[idx] = c;
                visit[c] = true;
                perm(idx+1);
                visit[c] = false;
            }
        }
    }
    static int check(){
        int nowDist = 0;
        char pre = 'S';
        for(int i = 0 ; i < 5; i++){
            int di = distStorage.get(pre).getOrDefault(sel[i],-1);
            if(di == -1)
                return -1;
            pre = sel[i];
            nowDist += di;
        }

        return nowDist;
    }
}

4. 마치며

오우 100줄이나 나올 문제였나..