[JAVA] 백준 25307 - 시루의 백화점 구경

문제

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

25307번: 시루의 백화점 구경

 

해결 방법

• 시루의 시작 위치에서 의자를 찾는 과정은 BFS를 돌리면 될 것이라 생각함
• 하지만 문제는 마네킹과의 거리가 K 이하인 곳을 방문하지 않아야 된다는 것
• 만약 모든 마네킹에서 각각 BFS나 DFS 등을 진행하여 갈 수 없는 곳들을 체크한다 마네킹이 최대 2000 * 2000 개 있을 수 있고 K가 최대 4000이기 때문에 시간초과가 발생함
• 이를 해결하기 위해서는 모든 마네킹의 위치를 큐에 넣고 BFS를 돌리면 됨
• 이 방식으로 BFS를 돌린다면 서로 다른 마네킹에서 뻗어가는 과정에서 생기는 중복을 제거할 수 있음

 

• 따라서 BFS를 총 두번 돌리면 문제가 해결되는데
• 첫번째 BFS는 모든 마네킹 위치를 큐에 넣고 돌려서 체크 배열에 마네킹과의 거리가 K이하인지 체크
• 두번째 BFS는 시루의 시작 위치부터 의자까지 찾아가는데, 입력에서의 기둥 위치와 첫번째 BFS에서 구한 체크 배열을 사용하면 됨

코드

• mannequinCheck 메소드가 첫번째 BFS(마네킹과의 거리가 K이하인지 체크)
• bfs 메소드가 두번째 BFS(시루가 의자를 찾아가는 작업)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p25307 {
    static int n, m, k;
    static int[][] arr;

    static int[] row = new int[]{0, 0, 1, -1};
    static int[] col = new int[]{1, -1, 0, 0};

    // 마네킹의 범위 내에 있는지 체크하는 배열
    static boolean[][] inMannequinRange;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   // 행
        m = Integer.parseInt(st.nextToken());   // 열
        k = Integer.parseInt(st.nextToken());   // 마네킹과 떨어져야 하는 거리

        arr = new int[n][m];
        inMannequinRange = new boolean[n][m];
        Point start = null;
        Queue<Point> mannequinList = new LinkedList<>();

        for(int i = 0 ; i < n ; i ++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < m ; j ++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                // 0:빈칸  1:기둥  2:의자  3:마네킹  4:시루의 시작위치
                if(arr[i][j] == 4) {
                    // 시루의 시작 위치
                    start = new Point(i, j, 0);
                } else if(arr[i][j] == 3) {
                    // 마네킹들의 위치
                    mannequinList.add(new Point(i, j, 0));
                    inMannequinRange[i][j] = true;
                }
            }
        }

        // 마네킹에서 K이하의 거리에 있는 지점들을 모두 체크
        mannequinCheck(mannequinList);

        // 시루의 시작 위치에서 의자를 찾아가는 bfs
        System.out.println(bfs(start.x, start.y));
    }

    static void mannequinCheck(Queue<Point> mannequinList) {
        while(!mannequinList.isEmpty()) {
            Point now = mannequinList.poll();
            if(now.dist == k) continue;     // 마네킹과의 거리가 k이상인 곳은 가면 안됨

            for(int i = 0 ; i < 4 ; i ++) {
                int nextX = now.x + row[i];
                int nextY = now.y + col[i];
                if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) continue;

                if(inMannequinRange[nextX][nextY] == false) {
                    inMannequinRange[nextX][nextY] = true;
                    mannequinList.add(new Point(nextX, nextY, now.dist + 1));
                }
            }
        }
    }

    static int bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y, 0));

        // 방문했는지 중복 체크에 사용하는 배열
        boolean[][] check = new boolean[n][m];
        check[x][y] = true;

        while(!queue.isEmpty()) {
            Point now = queue.poll();

            // 현재 위치가 의자라면 바로 return
            if(arr[now.x][now.y] == 2) {
                return now.dist;
            }

            for(int i = 0 ; i < 4 ; i ++) {
                int nextX = now.x + row[i];
                int nextY = now.y + col[i];
                if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) continue;

                // 다음에 갈 곳이 전에 방문한 적이 없고 && 기둥이 아니고 && 마네킹에서 K보다 멀리 떨어져 있는 경우
                if(check[nextX][nextY] == false && arr[nextX][nextY] != 1 && inMannequinRange[nextX][nextY] == false) {
                    queue.add(new Point(nextX, nextY, now.dist + 1));
                    check[nextX][nextY] = true;
                }
            }
        }

        // 이전에 의자를 찾지 못해서 여기까지 왔으므로 -1 return
        return -1;
    }

    static class Point {
        int x, y, dist;

        public Point(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}