문제 탐색하기

입력 자료 정리

1. 입력값 n은 배열의 행렬 크기다
2. h는 초기체력이고, d는 우산의 내구도를 의미한다
3. 이후 들어오는 nxn의 입력값은 각 인덱스의 값이다.
   들어오는값은 S, . U, E만 존재하며 각각 시작위치, 빈위치, 우산위치, 종료위치다

해결방법 추론

1. 입력크기가 크지 않기 떄문에 BFS에 탐색조건을 잘 섞는다면 쉽게 풀 수 있을 것이다
2. 하지만 이 문제에서 한가지 주의해야할 점이 있는데,
   이전에 탐색했던 위치를 다시 탐색할 수 있다는 점이다.
3. 따라서 단순 boolean 타입의 배열로는 해결할 수 없고, int형 배열을 사용해서 해결해야한다
4. int형 배열에는 최적의 선택만 할 수 있도록 현재 체력과 내구도를 넣어주도록 하자
5. 이때 최적의 경우만 탐색하기 위해,
   탐색 위치의 값이 현재 int형 방문배열에 있는 값보다 큰 경우만 탐색하도록 하자
   이렇게 한다면, E에 도달하는 순간이 최적의 순간이 될 것이고 바로 종료하면 된다!
6. U에 도달했을 때는 우산을 소유하면서 내구도를 1감소시키자.
   죽음의 비를 안 맞는 지역은 시작위치와 종료위치만이므로 우산이 있는 위치도
   죽음의 비가 내리기 때문이다
7. 시작위치를 지날 때는 비를 안 맞도록 하고, 그 이외의 위치는 우산소유여부에 따라
   체력이나 우산 내구도를 감소시키면서 탐색한다
8. 이렇게 했을 때, E에 도달하는 경우가 최소 이동 횟수가 될 것이다.

시간복잡도 계산

1. 시간복잡도는 BFS이므로 정점 + 간선의 개수가 될 것이다
2. 이때 nxn을 정점의 개수라 한다면, 간선의 개수는 탐색하는 범위가 될 것이다
3. 이때 탐색의 범위는 체력 + 우산내구도 x 우산의 개수가 될 것이다.
4. 따라서 시간복잡도는 O(nxn + h+(dxk))가 되며
   시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. 각 크기를 나탸내는 값은 변수로 관리하며,
   char형 2차원 배열에 각 인덱스 값을 관리한다
2. int형 2차원 방문배열을 사용해서 문제를 해결해나가자
3. 정답은 찾지 못했을 때를 대비하여 미리 -1로 초기화해둔다

구현 코드 설계

1. BFS에서 큐에 넣는 값은 차례대로,
   y좌표/x좌표/이동거리/현재체력/우산소유여부/우산현재내구도를 의미한다
2. 우산소유여부는 1과 0으로 구분짓고,
   1일때는 우산을 소유하고 있으며, 0일때는 우산을 소유하고 있지 않는 것을 판단한다
3. 현재 위치가 E일 경우 ans를 갱신하고 종료하며, 아닌경우 탐색을 계속한다
4. 주어진 조건에 맞춰서 BFS를 구현하고,
   방문배열에 대해서만 현재 체력 + 현재 우산 내구도로 갱신해준다

출력값 설계

1. BFS 탐색 결과 완성한 ans를 출력하면 정답이 된다.

정답 코드

import java.io.*;
import java.util.*;

public class Main {

    static char[][] arr;
    static int ans = -1;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        arr = new char[n][n];
        int[] start = new int[2];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = s.charAt(j);
                if(arr[i][j] == 'S'){
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        visited = new int[n][n];
        bfs(n,h,d, start[0], start[1]);

        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void bfs(int n, int h, int d, int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{y,x,0,h,0,0});
        visited[y][x] = h + d;
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(arr[now[0]][now[1]] == 'E'){
                ans = now[2];
                return;
            }

            if(now[5] == 0){
                now[4] = 0;
            }

            for (int i = 0; i < 4; i++) {
                int ny = now[0] + dy[i];
                int nx = now[1] + dx[i];
                if(ny >=0 && ny < n && nx >=0 && nx < n && visited[ny][nx] < now[3] + now[5]){
                    visited[ny][nx] = now[3] + now[5];
                    if(arr[ny][nx] == 'U'){
                        q.add(new int[]{ny,nx,now[2]+1, now[3], 1, d-1});
                        continue;
                    }

                    if(arr[ny][nx] == 'S'){
                        q.add(new int[]{ny,nx,now[2]+1, now[3], now[4], now[5]});
                        continue;
                    }

                    if(now[4] == 1){
                        q.add(new int[]{ny,nx,now[2]+1, now[3], now[4], now[5]-1});
                    }else{
                        q.add(new int[]{ny,nx,now[2]+1, now[3]-1, now[4], now[5]});
                    }

                }
            }


        }

    }

}

문제 링크

22944번 - 죽음의 비