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

문제내용

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

22944번: 죽음의 비

가로, 세로 길이가 N$N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지대라는 곳이다. 현재 있는 위치에도 곧 비가 내릴 예정이라 빨리 이 죽음의 비를 뚫고 안전지대로 이동해야한다.

다행히도 격자에는 죽음의 비를 잠시 막아주는 우산이 K$K$개 존재한다. 우산에는 내구도 D$D$라는 개념이 존재한다. 우산에 비를 맞으면 내구도가 1씩 감소하고, 내구도가 0이 되는 순간 우산은 사라진다. 문제에서 주어지는 우산의 내구도는 모두 D$D$로 동일하다.

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

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

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

입력

첫 번째 줄에 정사각형 격자의 한변의 길이인 N$N$와 현재 체력 H$H$, 우산의 내구도 D$D$가 공백으로 구분되어 주어진다.

다음 N$N$개의 줄에는 정사각형 격자의 정보가 N$N$개의 문자로 붙어서 주어진다. 이때 주어지는 문자는 우산은 "U", 현재 있는 위치 "S", 안전지대 "E", 빈 칸 "."만 존재한다. 현재 있는 위치 "S"와 안전지대 "E"는 반드시 1개 존재한다.

출력

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

제한

•  4≤N≤500$4 ≤ N ≤ 500$ 
•  0≤K≤10$0 ≤ K ≤ 10$ 
•  1≤H≤10,000$1 ≤ H ≤ 10,000$ 
•  1≤D≤5,000$1 ≤ D ≤ 5,000$ 
• 주어지는 모든 수는 정수이다.

---

문제풀이

간단하게 요약하면 상하좌우로 움직이면서 E로 도달하기만 하면되는거라 BFS로 풀면된다.

하지만 그냥 이전에 하던것처럼 방문배열을 boolean으로 하게되면 더 진행가능한 요소가 있음에도 이미 방문했던곳이라 진행을 멈춰야하는 경우가 생긴다.

이를 방지하기 위해 방문배열을 int형으로 바꿔서 진행해 준다.(방문배열없으면 무조건 시간초과임)

 

요소가 진행 가능한 거리를 "hp + 현재 우산내구도" 라고 한다면

int형으로 선언한 방문 배열에선 이전에 방문했던 요소가 현재 요소의 진행가능거리 보다 작다면 갱신해주고, 큐에 추가해준다. 즉, if (check[nx][ny] < hp + cost ) check[nx][ny] = hp + cost 가 된다.

 

이외에는 조건에 따라 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 Main {
	static int n,h,d;
	static char[][] map;
	static int[][] check;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static class Node{
		int x, y, h, cost, cnt;
		public Node(int x, int y, int h, int cost, int cnt) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.cost = cost;
			this.cnt = cnt;
		}
	}
	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());
		
		map = new char[n][n];
		check = new int[n][n];
		
		int startX=0, startY=0;
		for(int i=0; i<n; i++) {
			String str = br.readLine();
			for(int j=0; j<str.length(); j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j]=='S') {
					startX = i;
					startY = j;
				}
			}
		}
		
		int ans = BFS(startX, startY);
		System.out.println(ans);
	}
	
	//sx,sy : 시작위치
	public static int BFS(int sx, int sy) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(sx,sy,h,0,0));//시작점 추가
		check[sx][sy] = h;//시작점 방문처리
		
		int min = Integer.MAX_VALUE;//최소이동 거리
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			//상하좌우 탐색
			for(int i=0; i<4; i++) {
				int hp=cur.h, cost=cur.cost, cnt=cur.cnt;
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				//경계 바깥
				if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
				
				//E에 도달했으면 min갱신
				if(map[nx][ny]=='E') {
					min = Math.min(min, cnt+1);
					continue;
				}
				
				//우산이면 갈아치우기
				if(map[nx][ny]=='U') cost = d;
				
				//E,U는 위에서 처리했기 때문에 남은건 . 밖에 없음.
				if(cost!=0) cost--; //우산 내구도 있을떄
				else hp--; //없을떄
				
				//죽는경우는 다시 탐색
				if(hp==0) continue;
				
				//현재 요소가 전에 방문했던 요소보다 진행을 더 할수 있다 = 현재요소로 방문처리하기
				if(check[nx][ny]<hp+cost) {
					check[nx][ny] = hp+cost;
					q.add(new Node(nx, ny, hp, cost, cnt+1));
				}
			}
		}//while
		
		if(min==Integer.MAX_VALUE) return -1;//E에 도달 못함
		return min;//E에 도달함.
	}
}

---

마치며

비슷한 문제를 이전에 코테에서 못 풀었던 기억이 있다.. 그때는 배열의 요소들이 문자로 돼 있었는데 그게 좀더 어려운 문제였다. 아무튼 그때도 마찬가지로 단순하게 풀려고했으나 풀릴듯말듯 안풀린 경험이 있는데, 이 문제 덕분에 비슷한 문제에서 앞으론 해결법을 올릴수 있다는것에 만족한다.