[BOJ 22944] 죽음의 비

문제

---

N X N 격자가 있고, 현재 위치와 안전지대를 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내린다.
죽음의 비를 막아주는 우산 K개가 있는데, 우산에는 내구도 D라는 개념이 존재한다.
우산에 비를 맞으면 내구도가 1씩 감소하고, 내구도가 0이 되는 순간 우산은 사라진다.
문제에서 주어지는 우산의 내구도는 모두 D로 동일하다.

격자에서 이동을 할 때 다음과 같이 순서로 진행된다.

1. 상하좌우로 이동한다. 만약 이동할 곳이 격자 밖이라면 이동할 수 없다.
2. 이동한 곳이 안전지대라면 반복을 종료한다.
3. 이동한 곳에 우산이 있다면 우산을 든다. 만약, 이동할 때부터 우산을 가지고 있다면 가지고 있는 우산을 버리고 새로운 우산으로 바꾼다.
4. 버린 우산은 더 이상 사용할 수 없다.
5. 죽음의 비를 맞았을 때, 우산을 가지고 있다면 우산의 내구도가 1이 감소하고 만약 우산을 가지고 있지 않는다면 체력이 1 감소한다.
6. 만약 우산의 내구도가 0이 되면 들고 있는 우산이 사라진다.
7. 만약 체력이 0이 되면 죽는다...
8. 아직 체력이 남았다면 안전지대까지 위 과정을 반복한다.

현재 있는 위치에서 안전지대로 얼마나 빠르게 이동할 수 있는지 구하자.

첫 번째 줄에 격자 한변의 길이 N, 현재 체력 H, 우산 내구도 D가 공백으로 주어진다.
N개의 줄에는 정사각형 격자의 정보가 N개의 문자로 붙어서 주어진다.
우산은 'U', 현재 있는 위치는 'S', 안전지대는 'E', 빈칸은 '.' 으로 주어지고, 'S'와 'E'는 반드시 1개 존재한다.

안전지대로 이동할 때 최소 이동 횟수를 출력한다. 만약 안전지대로 이동하지 못하는 경우에는 -1을 출력한다.

[풀이 코드]

---

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

public class 죽음의_비 {
	static int N, H, D, result, s_r, s_c;
	static char[][] arr;
	static int[] dr = {0, 0, 1, -1};
	static int[] dc = {1, -1, 0, 0};
	
	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());
		H = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		arr = new char[N][N];
		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') {
					s_r = i;
					s_c = j;
				}
			}
		}
		
		result = bfs(s_r, s_c);
		System.out.println(result);
	}
	
	static class Point {
		int r, c, cnt, stemina, um_cnt;
		Point(int r, int c, int cnt, int stemina, int um_cnt) {
			this.r=r;
			this.c=c;
			this.cnt=cnt;
			this.stemina=stemina;
			this.um_cnt=um_cnt;
		}
	}
	private static int bfs(int r , int c) {
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(new Point(r, c, 0, H, 0));
		int[][] v = new int[N][N];
		v[r][c] = H;
		
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			if(arr[p.r][p.c]=='E') return p.cnt;
			for (int d = 0; d < 4; d++) {
				int nr = p.r+dr[d];
				int nc = p.c+dc[d];
				
				if(nr<0 || nr>=N || nc<0 || nc>=N) continue;
				
				int stemina = p.stemina;
				int um_cnt = p.um_cnt;
				
				if(arr[nr][nc] == 'U') {
					um_cnt = D;
				}else {
					if(um_cnt>0) {
						um_cnt--;
					}else {
						stemina--;
					}
				}
				if(v[nr][nc] >= um_cnt+stemina) continue;
				
				queue.offer(new Point(nr, nc, p.cnt+1, stemina, um_cnt));
				v[nr][nc]=um_cnt+stemina;
			}
		}
		return -1;
	}
}

처음에 방문배열 v를 boolean 형으로 2차원 배열로 사용했지만, 한번 방문했던 위치에도 다시 방문해야 하기 때문에 당연히 제출했을 때, '틀렸습니다' 가 나왔다.
그래서 v를 boolean 형으로 3차원 배열로 만들어서 풀었더니 '시간초과' 가 나왔고, 4차원 배열로 만들었더니 '메모리 초과'가 나왔다.

시간과 메모리를 동시에 잡으면서 문제를 풀 수 있느 방법을 생각해봤을 때, 계산한 (체력+우산내구도)가 해당 위치에 있는 (체력+우산내구도)보다 클 경우에만 queue에 넣어주는 방식을 생각했다. 그래서 v를 int형으로 선언하고 조건문을 추가했더니 풀렸다.

같은 위치라도 상태가 다르면 다르게 취급해야 하는 탐색 문제에서는 BFS와 메모이제이션을 잘 섞는게 중요하다는 걸 느꼈다.