[백준]25307: 시루의 백화점 구경(java)

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

25307번: 시루의 백화점 구경

문제

시루는 부모님과 함께 백화점에 갔다. 부모님은 쇼핑할 것이 많기 때문에 여러 곳을 돌아다녀야 하고, 시루는 부모님과 함께 걸어다니는 것이 너무 힘들어서 의자에 앉아서 쉬려고 한다.

백화점은 세로 길이가 N$N$, 가로 길이가 M$M$인 격자 형태이고, 상하좌우로 인접한 칸으로 이동할 때마다 1 만큼의 체력을 소모한다. 시루는 현재 위치에서 출발해 백화점 곳곳에 있는 의자 중 하나를 찾아가서 앉으려고 한다. 시루는 백화점 밖으로 나가면 부모님께 혼나기 때문에 백화점 밖으로 나갈 수 없다.

백화점에는 건물을 지탱하기 위한 기둥과 옷을 전시하기 위한 마네킹이 있다. 시루는 기둥이 있는 칸으로 이동하지 못하고, 마네킹을 무서워하기 때문에 마네킹과 거리가 K$K$ 이하인 칸은 사용하지 않으려고 한다. 이때 두 칸 (rx,cx),(ry,cy)$(r_x, c_x), (r_y, c_y)$의 거리는 |rx−ry|+|cx−cy|$\vert r_x-r_y \vert + \vert c_x-c_y \vert$이다. 단, 시루가 출발할 때는 부모님과 함께 있기 때문에, 출발 지점과 마네킹과의 거리가 K$K$ 이하가 되어도 출발할 수 있다.

시루는 다리가 너무 아프기 때문에 체력 소모를 최소화하면서 의자까지 찾아가려고 한다. 시루가 소모하는 체력의 최솟값을 구해보자.

입력

첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 N,M,K$N, M, K$가 공백으로 구분되어 주어진다. (1≤N,M≤2000$1 \leq N,M \leq 2\,000$, 0≤K≤4000$0 \leq K \leq 4\,000$)

둘째 줄부터 N$N$개의 줄에 각각 M$M$개씩 위에서부터 차례로 백화점의 상태가 주어진다. 아무것도 없는 칸은 0, 기둥이 있는 칸은 1, 의자가 있는 칸은 2, 마네킹이 있는 칸은 3, 시루의 시작 위치는 4로 주어진다. 시루의 시작 위치는 정확히 한 번 주어지고, 해당 위치에 기둥, 의자, 마네킹이 존재하지 않는다.

출력

시루가 의자를 찾아갈 수 있다면 시루가 소모하는 체력의 최솟값을 출력한다.

만약 의자를 찾아갈 수 없다면 -1을 출력한다.

예제 입력 1 

5 5 1
0 0 0 0 4
0 0 0 1 0
0 0 0 0 3
0 0 0 1 0
0 0 0 0 2

예제 출력 1 

8

---

풀이

시루는 마네킹을 무서워해 K 거리만큼 다가가지 않는다. 즉, 시루는 현재 위치로부터 마네킹, 벽을 피해 최단거리로 의자로 갈 수 있는 거리를 구하면 된다.

저같은경우는 그래프 문제에서 dfs, bfs를 푸는데 규칙을 이렇게 둡니다.

최단거리, 최소시간, 가장 짧은 이라는 말이있다면 bfs

모든 경로를 훑어야 하는 경우 즉, A to B를 가더라도 여러가지 경우의수가 존재하면 dfs를 사용합니다.

 

1. 마네킹으로부터 K의 거리를 visited = true 로 처리해준다.

> 시루가 나중에 bfs에서 움직일 때 그 곳을 밟지 않도록 해줍니다.

public static void dfs(int x, int y, int depth) {
    if(depth == K) {
        return;
    }

    for(int i=0; i<4; i++) {
        int nx = x + dist[i][0];
        int ny = y + dist[i][1];

        if(!isIn(nx, ny) || visited[nx][ny]) continue;
        visited[nx][ny] = true;
        dfs(nx, ny, depth+1);
    }
}

2. 시루가 움직입니다. 도착까지의 최단거리를 구합니다. 일반적인 bfs와 같습니다.

public static void bfs() {
    Queue<Point> q = new LinkedList<>();
    q.add(start);
    visited[start.x][start.y] = true;
    int depth = 0;

    while(!q.isEmpty()) {
        int len = q.size();

        for(int l=0; l<len; l++) {
            Point now = q.poll();

            for(int i=0; i<4; i++) {
                int nx = now.x + dist[i][0];
                int ny = now.y + dist[i][1];

                if(!isIn(nx, ny) || visited[nx][ny]) continue;
                if(finish.x == nx && finish.y == ny) {
                    System.out.println(depth+1);
                    return;
                }
                visited[nx][ny] = true;
                q.add(new Point(nx, ny));
            }
        }
        depth++;
    }

    System.out.println(-1);
}

 

전체 풀이

package 백준;

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

public class BJ_G4_25307_시루의백화점구경 {
    static class Point{
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M, K;
    static int[][] map;
    static boolean[][] visited;
    static Point start = null, finish = null;
    static int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    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());
        K = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 4) {
                    start = new Point(i, j);
                } else if(map[i][j] == 3) {
                    // dfs를 통해서 K거리까지 시루가 이동하지 않게 visited에 체크해줌
                    visited[i][j] = true;
                    dfs(i, j, 0);
                } else if(map[i][j] == 2) {
                    finish = new Point(i, j);
                }
            }
        }
        //early return
        if(finish == null) {
            System.out.println(-1);
            return;
        }

        bfs();
    }

    public static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.add(start);
        visited[start.x][start.y] = true;
        int depth = 0;

        while(!q.isEmpty()) {
            int len = q.size();

            for(int l=0; l<len; l++) {
                Point now = q.poll();

                for(int i=0; i<4; i++) {
                    int nx = now.x + dist[i][0];
                    int ny = now.y + dist[i][1];

                    if(!isIn(nx, ny) || visited[nx][ny]) continue;
                    if(finish.x == nx && finish.y == ny) {
                        System.out.println(depth+1);
                        return;
                    }
                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny));
                }
            }
            depth++;
        }

        System.out.println(-1);
    }

    public static void dfs(int x, int y, int depth) {
        if(depth == K) {
            return;
        }

        for(int i=0; i<4; i++) {
            int nx = x + dist[i][0];
            int ny = y + dist[i][1];

            if(!isIn(nx, ny) || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            dfs(nx, ny, depth+1);
        }
    }

    public static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}