[Algorithm] 백준/16469 :: 소년 점프

* 핵심

악당 무리 3명이 같이 방문하는 점을 어떻게 찾을 것인지?

visited를 boolean이 아닌 int배열로 주고 for문을 돌면서 i 값마다 비트연산으로 확인함    >> 악당 3명이 방문한 점은 111 이니까 7이 된다.

TreeMap을 이용하여 최소 지점의 개수를 출력

* 문제

문제

한국 힙합의 떠오르는 신성인 마미손은 악당 무리에게서 도망치고 있다. 악당 무리는 넉살, 스윙스, 창모 3명으로 이루어져 있다. 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다. 뒤늦게 미로에 도착한 악당 무리는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다. 이때 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다. 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다. 넉살, 스윙스, 창모는 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신한다. 마미손은 숨기 이전에 악당들이 어디서 탐색을 시작할지 알고 있어 악당들이 찾아올 지점들을 피해 숨으려고 한다. 

힘든 모험을 시작한 마미손. 이 모험에서 주인공은 절대 죽지 않는다는 것을 여러분이 마미손이 되어 보여주자! R*C 크기의 미로가 주어지고, 넉살, 스윙스, 창모의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 되는 지점을 마미손에게 알려주자. 

입력

첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 길, 1은 벽을 나타낸다. 그 다음 줄부터 3개의 줄은 각각 넉살, 스윙스 창모의 위치(행, 열)를 나타내는 자연수 Xi, Yi가 (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C)주어진다. 악당들은 위치가 겹치지 않고, 항상 이동 가능한 길에서 출발한다. 맨 왼쪽 위의 위치는 (1, 1)이다. 

출력

첫째 줄에 한 지점에 세 악당이 모일 때 걸린 시간의 최소 값을 출력한다. 둘째 줄에는 그러한 지점의 개수를 출력한다. 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static int[][] map, res;
    public static int[][] visited;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        int r = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
 
        map = new int[r][c];
        res = new int[r][c];
        visited = new int[r][c];
 
        for (int i = 0; i < r; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
 
        ArrayList<pair> badboy = new ArrayList<>();
 
        for (int i = 0; i < 3; i++) {
            stk = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());
            badboy.add(new pair(x - 1, y - 1, 0));
        }
        for (int i = 0; i < 3; i++) {
            pair p = badboy.get(i);
            Queue<pair> q = new LinkedList<>();
            q.add(new pair(p.x, p.y, 0));
            while (!q.isEmpty()) {
                p = q.poll();
                if ((visited[p.x][p.y] & 1 << i) == 0) {    // 비트 연산을 통한 악당 3명의 방문 여부 확인 
                    visited[p.x][p.y] += 1 << i;
                    res[p.x][p.y] = Math.max(res[p.x][p.y], p.w);
                    for (int j = 0; j < 4; j++) {
                        int nx = p.x + dx[j];
                        int ny = p.y + dy[j];
                        if (nx >= 0 && nx < r && ny >= 0 && ny < c && map[nx][ny] == 0)
                            q.add(new pair(nx, ny, p.w + 1));
                    }
                }
            }
        }
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (visited[i][j] == 7) {
                    if (tm.containsKey(res[i][j])) {
                        tm.put(res[i][j], tm.get(res[i][j]) + 1);
                    } else {
                        tm.put(res[i][j], 1);
                    }
                }
            }
        }
        if (tm.size() == 0) System.out.println("-1");
        else System.out.println(tm.firstEntry().getKey() + "\n" + tm.firstEntry().getValue());
    }
 
    public static class pair {
        int x, y, w;
 
        public pair(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
}