[22944] 백준 - 죽음의 비(JAVA)

[ 풀이 방법 ]

- 그냥 bfs를 돌렸다가는 시간초과가 나기때문에, 백트래킹을 해주어야 한다.

 

 

1. S의 위치에서 BFS탐색을 진행하며 E까지 도달할 수 있는지 찾는다.

 

 

2. boolean을 이용하여 방문처리를 할 경우, 우산을 획득하고나서 지나가는 경우를 처리하지 못 한다.
     따라서, int형으로 방문처리를 해 주어야 한다.

이미 그 자리에 방문했던 목숨 값  <  현재 목숨 값 + 지닌 우산 내구도

이 경우에는 전에 방문했을 때보다 더 먼 거리를 나아갈 수 있으므로 queue에 넣어준다.

 

 

왼쪽, 오른쪽 모두 4번만에 [1, 3]에 도달할 수 있다.
bfs의 사방탐색 순서에 따라 왼쪽의 경우가 먼저 처리되어 true처리를 하게 되면,
오른쪽처럼 다른 방법으로 더 많은 목숨으로 앞으로 더 많이 나아갈 수 있는 경우를 처리하지 못한다.

 

 

왼쪽의 경우,
[1, 3]을 도달했을 때, 앞으로 나아갈 수 있는 크기는 0이다.
오른쪽의 경우는,
[1, 3]을 도달했을 때, 앞으로 나아갈 수 있는 크기는 목숨(2) + 현재 남은 우산의 내구도(1)이다.

 

 

따라서, 방문처리는
전에 그 위치를 방문했던 크기보다,
현재 목숨 + 현재 가진 우산의 내구도의 합이 더 큰 경우로 해준다.
(앞으로 더 많은 곳으로 나아갈 수 있기 때문이다.)

 

 

 

 

3. BFS탐색을 하는 동안,
    - 우산을 가지고 있다면 목숨 말고, 우산의 내구도 감소시키기
    - 우산을 가질 수 있다면, 우산을 줍기
    - 목숨이 0이되어 더이상 나아갈 수 없는 경우를 다 처리 해준다.

 

 

4. 무사히 E에 도달한다면 현재까지의 이동 횟수를 출력한다.

 

 

5. 만약 BFS탐색 도중 모두 죽어, E까지 도저히 갈 수가 없다면 -1을 출력한다.

 

 

 

 

 

 

[ 전체 코드 ]

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 Main {
    static class Position {
        int r;		// 행
        int c;		// 열
        int u;		// 가지고있는 우산 내구도
        int life;	// 현재 목숨

        public Position(int r, int c, int u, int life) {
            this.r = r;
            this.c = c;
            this.u = u;
            this.life = life;
        }
    }

    static Position player;
    static int N, H, D, route = -1;
    static char[][] matrix;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static int[][] isVisited;

    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());   // 한 변 길이
        H = Integer.parseInt(st.nextToken());   // 현재 체력
        D = Integer.parseInt(st.nextToken());   // 우산 내구도

        matrix = new char[N][N];
        for (int r = 0; r < N; r++) {
            matrix[r] = br.readLine().toCharArray();
            for (int c = 0; c < N; c++) {
                if (matrix[r][c] == 'S')
                    player = new Position(r, c, 0, H);
            }
        }

        isVisited = new int[N][N];
        bfs();

        System.out.println(route);
    }

    private static void bfs() {
        Queue<Position> queue = new LinkedList<>();
        isVisited[player.r][player.c] = player.life;
        queue.offer(player);

        int cnt = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (--size >= 0) {
                Position p = queue.poll();

                for (int i = 0; i < 4; i++) {
                    int nr = p.r + dr[i];
                    int nc = p.c + dc[i];

                    if (nr < 0 || nc < 0 || nr >= N || nc >= N)
                        continue;

                    if (matrix[nr][nc] == 'E') {
                        route = cnt + 1;
                        return;
                    }

                    int nu = p.u, nlife = p.life;
                    if (matrix[nr][nc] == 'U')
                        nu = D;

                    if (nu != 0)
                        nu--;   // 우산 내구도 감소
                    else
                        nlife--;    // 목숨 감소

                    if (nlife == 0)
                        continue;

                    if (isVisited[nr][nc] < nlife + nu) {
                        isVisited[nr][nc] = nlife + nu;
                        queue.offer(new Position(nr, nc, nu, nlife));
                    }
                }
            }
            cnt++;
        }
    }
}