백준 16469 (소년 점프) - java

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

16469번: 소년 점프

 

문제

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

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

 

유형 : BFS

 

접근 방식

• 처음에는 '구슬 탈출' 문제 처럼 악당 3명의 위치를 모두 넣고 한번에 탐색해야 하는가 생각했다. 하지만 이렇게 할 경우 시간 복잡도가 감당이 안된다고 생각했다.
• 주의해야 할 점은 단 하나 '악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다.' 제자리에 있는 경우는 탐색에 있어 방문 거리 최소값을 부시는 개념이기 때문에 피곤하다....
• 문제를 해결하는 방법은 생각 외로 간단하다.
  • 우선 악당 3명을 각각 BFS 탐색한다. (3차원의 방문 거리 배열)
  • 방문 거리 배열의 각 위치 (100 * 100)을 비교한다.
    • 넉살이 10, 스윙스가 15, 창모가 9인 위치가 있다고 가정하자.
    • 해당 위치에서 3명은 언제 만날까???? -> 가장 큰 값인 15이다.
    • 넉살과 창모는 스윙스가 도착할 때까지 가만히 있으면 되는 것이다!!!!!
  • 즉 방문 배열 3개의 값중 큰값이 최소가 되는 값과 해당 위치 개수를 구하면 끝인 문제이다!!!!

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int[][] arr;
    static int[][][] v;

    static int[] dx  = {0,0,-1,1};
    static int[] dy  = {1,-1,0,0};

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        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+1][m+1];
        for(int i=1;i<=n;i++){
            String line = br.readLine();

            for(int j=1;j<=m;j++){
                arr[i][j] = line.charAt(j-1) - '0';
            }
        }

        v = new int[n+1][m+1][3];

        for(int i=0;i<3;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            bfs(x,y,i);
        }


        int num = 0;
        int sec = Integer.MAX_VALUE;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){

                if(arr[i][j] == 1)
                    continue;

                if(v[i][j][0] == 0 || v[i][j][1] == 0 || v[i][j][2] == 0)
                    continue;

                int tmp = Math.max(Math.max(v[i][j][0],v[i][j][1]),v[i][j][2]);

                if(sec > tmp){
                    sec = tmp;
                    num = 1;
                }else if(sec == tmp){
                    num += 1;
                }

            }
        }

        if(sec != Integer.MAX_VALUE) {
            System.out.println(sec - 1);
            System.out.println(num);
        }else{
            System.out.println(-1);
        }

        br.close();

    }

    static void print(int num){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(v[i][j][num]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void bfs(int x,int y,int num){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));
        v[x][y][num] = 1;

        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;

                if(arr[nx][ny] == 1)
                    continue;


                if(v[nx][ny][num] == 0){
                    v[nx][ny][num] = v[cur.x][cur.y][num] + 1;
                    q.add(new Node(nx,ny));
                }
            }
        }
    }
}
class Node{
    int x;
    int y;

    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}