[백준] 22944번 죽음의 비 JAVA

문제

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

22944번: 죽음의 비

 

---

풀이 방법

풀이

문제에서 사람은 항상 목적지 아니면 우산이 존재하는 곳을 향해야만 최적의 이동을 할 수 있다.

따라서 시작위치, 우산위치, 목적지를 정점으로 재구성한 뒤 BFS를 수행한다.

 

 

설명

1. 안전 지대로 바로 가는 것이 가능 하다면 이 경우가 최소 이동 횟수이다.

2. 안전 지대로 바로 가지 못한다면 안가본 우산위치 중 하나의 위치로 가야한다.

 

최소 이동 거리라는 조건을 만족하기 위해 사람은 현재위치 ~ 우산 위치  혹은 현재 위치 ~ 안전 지대로 갈 때에 맨하탄 거리만큼만 이동할 것이다. 따라서 시작위치, 우산 위치, 안전 지대를 정점으로 만든 뒤 간선의 가중치를 맨하탄 거리로 생각하고, 현재 체력과 우산 내구도를 이용해서 정점과 정점 사이를 갈 수 있는 지 확인하며 BFS를 진행한다.

 

 

 

현재 체력으로 E로 바로 갈 수 있기 때문에 바로 방문하는 케이스

 

---

현재 체력으로 E로 바로 갈 수 없기 때문에 다른 우산 지점을 방문한다.

현재 체력으로 우산까지 갈 수 있기 때문에 방문한다.

 현재 체력(체력 +  우산 내구도)로 E 까지 갈 수 있으므로 방문한다.

---

코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_22944_죽음의비 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
	static int N,H,D, minDist = Integer.MAX_VALUE;
	static Integer[] start = new Integer[2];
	static Integer[] end = new Integer[2];
	static ArrayList<Integer[]>u = new ArrayList<>();
	
	//현재 위치, 현재까지 온 거리, 이때 까지 방문한 우산들, 현재 체력, 현재 우산 내구도
	static class Status{
		Integer[] pos;
		int dist;
		int[] visited;
		int hp;
		int umbHP;
		public Status(Integer[] pos, int dist, int[] visited, int hp, int umbHP) {
			super();
			this.pos = pos;
			this.dist = dist;
			this.visited = visited;
			this.hp = hp;
			this.umbHP = umbHP;
		}
	}
	
	public static void main(String[] args) throws Exception {
		init();
		
		Queue<Status>q = new ArrayDeque<Status>();
		q.add(new Status(start,0,new int[u.size()],H,0));
		
		while(!q.isEmpty()) {
			Status curr = q.poll();
			
			//가지치기를 해도 시간이 똑같음... 머지?
//			if(curr.dist > minDist) {
//				continue;
//			}
			
			// 1. 안전 지대로 갈 수 있는지 확인
			if(canGo(curr.pos, end, curr.hp+curr.umbHP)) {
				
				int d = curr.dist+getDist(curr.pos, end);
				if(minDist > d) {
					minDist = d;
				}
				continue;
			}
			
			// 2. 우산 위치로 갈 수 있는지 확인
			for(int i=0;i<u.size();i++) {
				if(curr.visited[i]==1)continue;
				
				if(canGo(curr.pos,u.get(i),curr.hp+curr.umbHP)) {
					
					//방문처리 한 배열을 넘겨 준다.
					int[] tmpvisited = new int[u.size()];
					for(int j=0;j<u.size();j++) {
						tmpvisited[j] = curr.visited[j];
					}
					tmpvisited[i] = 1;
					

					int d = getDist(curr.pos, u.get(i));
					if(curr.umbHP >= d) {
						q.add(new Status(u.get(i), curr.dist+d, tmpvisited, curr.hp, D-1));
					}
					else {
						q.add(new Status(u.get(i), curr.dist+d, tmpvisited, curr.hp+1-(d-curr.umbHP), D-1));
					}
					
				}
			}
		}
		
		if(minDist == Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(minDist);
		}
		
	}
	
	
	// 거리가 현재 체력보다 크다면 갈 수 없음
	static boolean canGo(Integer[] start, Integer[] end, int leftHp) {
		int dist = getDist(start, end);
		if(dist > leftHp)return false;
		return true;
	}
	
	static int getDist(Integer[] a, Integer[]b) {
		return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
	}
	
	static void init()throws Exception{
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		for(int i=0;i<N;i++) {
			String s = in.readLine();
			for(int j=0;j<N;j++) {
				char tmp = s.charAt(j);
				if(tmp == 'S') {
					start[0] = i;
					start[1] = j;
				}
				else if(tmp == 'E') {
					end[0] = i;
					end[1] = j;
				}
				else if(tmp == 'U') {
					u.add(new Integer[] {i,j});
				}
			}
		}
	}
}