[BOJ/백준] 27314 - 러키☆한별

27314번: 러키☆한별

---

선물이 먼저 도착해서 기다린다면?

---

---

• 제목

러키☆한별

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

한별이는 운이 매우 좋다!

한별이는 벽, 다른 사람들, 그리고 여러 개의 출구가 있는 미로를 탈출하고자 한다.

미로 내에서 한별이와 다른 사람들은 매 순간 상하좌우 중 한 방향으로 한 칸 이동할 수 있다. 또, 한별이가 아닌 다른 사람들은 멈춰있을 수도 있다. 벽이 있는 칸으로 이동하거나 미로 격자 밖으로 나가는 것은 불가능하다. 여러 명이 같은 칸에 있는 것은 가능하다.

한별이를 제외한 사람들은 모두 한별이에게 줄 선물을 하나씩 가지고 있다. 만약 한별이와 선물을 가진 사람이 같은 칸에 있으면, 그 사람은 한별이에게 선물을 준다.

한별이는 한별이가 도달할 수 있는 미로의 출구 중 하나를 골라 이로 향하는 최단경로 중 하나를 고르고, 이를 따라 이동한다. 한별이를 제외한 다른 사람들은 한별이의 경로를 알고, 한별이에게 선물을 주기 위한 최적의 경로로 이동한다.

한별이가 어떤 칸에서 다른 칸으로 이동하면, 도착한 칸에 이미 있던 사람들과, 그 칸에 한별이와 동시에 도착한 사람들에게 선물을 받는다. 그 뒤 만약 도착한 칸이 한별이가 처음에 정한 출구면, 즉시 미로를 탈출한다. 다른 사람들은 어떤 출구에 도착해도 미로를 탈출하지 않는다.

한별이는 운이 매우 좋기 때문에, 항상 가능한 최대의 선물을 받는다. 한별이가 출구와 최단경로를 적절히 고르고, 사람들이 적절히 움직였을 때 한별이가 받을 수 있는 선물의 최대 개수를 구하시오.

---

• 입력

첫 번째 줄에 미로의 높이 N과 너비 M이 공백으로 구분되어 주어진다. (1 ≤ N, M, N * M ≤ 100, 000)

다음 N개의 줄에 미로의 정보가 길이 M인 문자열로 주어진다.

문자열에서 H는 한별이를 뜻하고, 미로 안에 정확히 한 번 나타난다.

문자열에서 P는 한별이가 아닌 다른 사람을 뜻하고, 미로 안에 최소 1번, 최대 100번 나타난다.

문자열에서 #은 출구를 뜻하고, 미로 안에 최대 100번 나타난다.

문자열에서 .는 빈 공간을 뜻한다.

문자열에서 X는 벽을 뜻한다.

한별이가 도달할 수 있는 출구가 하나 이상 존재함이 보장된다.

---

• 출력

한별이가 받을 수 있는 선물의 최대 개수를 출력한다.

---

예제 입력1	예제 출력1
4 3 #.. ..H .P. .P.	1

예제 입력2	예제 출력2
4 3 #X. .XH .P. .P.	2

예제 입력3	예제 출력3
4 4 #PPH X..P PPPP #XXX	7

예제 입력4	예제 출력4
1 5 H#.P#	1

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N, M;
    static char[][] arr;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    static int[][][] distance;

    static void BFS(int idx, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[N * M];
        visited[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            int x = curr / M;
            int y = curr % M;
            for (int k = 0; k < 4; k++) {
                int tx = x + dx[k];
                int ty = y + dy[k];
                if (tx < 0 || ty < 0 || tx >= N || ty >= M) continue;
                if (visited[tx * M + ty]) continue;

                if (arr[tx][ty] == 'X') continue;
                distance[idx][tx][ty] = distance[idx][x][y] + 1;
                visited[tx * M + ty] = true;
                queue.add(tx * M + ty);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int hanbyul = 0;
        arr = new char[N][M];
        ArrayList<Integer> exit = new ArrayList<>();
        ArrayList<Integer> friend = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = temp.charAt(j);
                if (arr[i][j] == '#') exit.add(i * M + j);
                if (arr[i][j] == 'H') hanbyul = i * M + j;
                if (arr[i][j] == 'P') friend.add(i * M + j);
            }
        }

        distance = new int[friend.size() + 1][N][M];
        for (int i = 0; i < friend.size(); i++) {
            BFS(i + 1, friend.get(i));
        }
        BFS(0, hanbyul);

        int answer = 0;
        for (int i = 0; i < exit.size(); i++) {
            int count = 0;
            int x = exit.get(i) / M;
            int y = exit.get(i) % M;
            int std = distance[0][x][y];
            for (int j = 0; j < friend.size(); j++) {
                if(distance[j + 1][x][y] == 0) continue;
                if(std >= distance[j + 1][x][y]) count++;
            }
            answer = Math.max(answer, count);
        }
        System.out.println(answer);
    }
}