[백준/BOJ] 22944번 죽음의 비 자바 풀이

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

22944번: 죽음의 비

 

문제

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

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

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

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

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

입력

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

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

출력

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

 

 

 

개인적으로 재밌게 풀었던 문제다.

최소 이동 횟수를 구하는 문제이므로 바로 BFS로 접근했다.

N*N 범위 안에서 상하좌우로 이동하며 큐에 넣어준다.

큐에 행과 열, 이동 횟수, 체력, 우산여부, 우산이 있다면 우산의 내구도 까지 저장해야 하므로

Rain이라는 class를 만들었다.

생성자로 위의 값을 가지는 객체 생성하고 큐에 넣는다.

 

이때 일반적인 BFS와 다른 점은 visit를 어떻게 처리해줄 것인지이다.

일반적인 BFS는 visit를 boolean 타입으로 정의하고 

true면 이미 방문한 것이므로 방문하지 않고, false면 방문하지 않았으므로 방문처리 해준다.

 

이 문제에서는

우산을 안 든채로 어떤 위치에 방문했을 때, 그 경로가 목적지까지 도달할 수 없지만

우산을 든채로 조금 돌아간다면 목적지까지 도달할 수 있는 경우가 존재할 수 있다.

이 경우의 반례는 아래와 같다.

 

4 2 10

...U

...S

....

E...

(answer: 7)

시작위치에서 바로 E로 간다면 7번이 아닌 5번만으로 갈 수 있겠지만, 

체력이 2밖에 되지 않으므로 우산없이는 갈 수 없다.

즉, S에서 U로 간 후 E로 가야한다.

이때 visit를 true/false로 처리해준다면

U가 0x0에서 1x0으로 갈 때 이미 S가 우산 없이 방문했기 때문에 갈 수 없어 answer가 -1으로 출력될 것이다.

 

 

이를 해결하기 위해 visit에 현재 체력 + 내구도를 저장한다.

만약 visit에 저장되어 있는 값이 현재 체력 + 내구도 보다 크거나 같다면

이미 지금 가려는 경로보다 효율적인 방법으로 방문했다는 의미이기 때문에 큐에 삽입하지 않고 continue 해준다.

하지만 visit에 저장되어 있는 값이 현재 체력 + 내구도 보다 작다면

아직 방문하지 않았거나, 지금 가려는 경로가 더 효율적이라는 의미이기 때문에 큐에 삽입해준다.

 

 

또 주의할 사항은 

<  죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지대라는 곳이다. > 라는 문제 속 조건이다.

즉, U에서도 죽음의 비가 내린다는 의미다.

U를 만난 경우 우산의 내구도를 D로 해주는 것이 아닌,

U에서도 우산을 든 후 비를 맞기 때문에 D - 1를 해주면 된다.

 

 

나머지 U인 경우, .인 경우, E인 경우는 각각

문제에 나와있는 조건대로 체력/내구도를 1씩 감소시키는 등의 처리를 해주면 된다.

 

 

 

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

public class Main {
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int N, H, D;
	static int answer = -1;
	static char[][] board;
	static int[][] visit; // 우산 내구도 + 체력을 저장

	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());

		board = new char[N][N];
		visit = new int[N][N];

		int startR = 0, startC = 0;
		boolean flag = false;

		for(int i=0;i<N;i++) {
			board[i] = br.readLine().toCharArray();
			if(!flag)
				for(int j=0;j<N;j++) {
					if(board[i][j] == 'S') {
						startR = i;
						startC = j;
						flag = true;
					}
				}
		}
		
		BFS(startR, startC);
		System.out.println(answer);

	}

	static void BFS(int startR, int startC) {
		Queue<Rain> q = new LinkedList<>();
		q.offer(new Rain(startR, startC, H, 0, false, 0));
		visit[startR][startC] = H;

		while(!q.isEmpty()) {
			Rain now = q.poll();

			for(int i=0;i<4;i++) {
				int nextR = now.r + dir[i][0];
				int nextC = now.c + dir[i][1];

				if(nextR < 0 || nextR >= N || nextC < 0   || nextC >= N)
					continue;

				if(board[nextR][nextC] == 'U') { // 다음 위치에 우산이 있다면 우산을 듦
					if(visit[nextR][nextC] >= now.h + D - 1)
						continue;
					visit[nextR][nextC] = D - 1 + now.h;
					q.offer(new Rain(nextR, nextC, now.h, now.cnt + 1, true, D - 1));
				}
				else if(board[nextR][nextC] == '.') { // 죽음의 비
					if(now.umbrella) { // 우산을 가지고 있다면 우산 내구도 - 1
						if(visit[nextR][nextC] >= now.h + now.umbrellaH - 1) 
							continue;
						if(now.umbrellaH - 1 == 0) // 우산의 내구도가 0이라면 우산이 사라짐
							q.offer(new Rain(nextR, nextC, now.h, now.cnt + 1, false, 0));
						else 
							q.offer(new Rain(nextR, nextC, now.h, now.cnt + 1, true, now.umbrellaH - 1));
						visit[nextR][nextC] = now.h + now.umbrellaH - 1;
					}
					else { // 우산이 없다면 체력 - 1
						if(now.h - 1 == 0 || visit[nextR][nextC] >= now.h - 1) // 체력이 0이라면 죽음
							continue;
						visit[nextR][nextC] = now.h - 1;
						q.offer(new Rain(nextR, nextC, now.h - 1, now.cnt + 1, false, 0));
					}
				}
				else if(board[nextR][nextC] == 'E') {
					answer = now.cnt + 1;
					return;
				}
			}
		}
	}

	static class Rain {
		boolean umbrella = false; // 우산 여부
		int umbrellaH = 0; // 우산 내구도
		int r, c, h; // 행, 열, 체력
		int cnt; // 이동 횟수

		Rain(int r, int c, int h, int cnt, boolean umbrella, int umbrellaH) {
			this.r = r;
			this.c = c;
			this.h = h;
			this.cnt = cnt;
			this.umbrella = umbrella;
			this.umbrellaH = umbrellaH;
		}
	}

}