[백준] 22944번 죽음의 비 문제 풀이

 

22944 - 죽음의 비

위 텍스트를 클릭하면 문제 링크로 이동합니다.

풀이 

 

문제 핵심

  문제에서 요구하는 것은 세 가지 입니다. 죽지 않고(조건1) 최단 거리로(조건2) 안전지대에 도착(조건2) 할 수 있는지 여부를 체크하는 것입니다. 코드 상에는 움직이는 사람의 체력을 저장하여 죽지 않고 이동할 수 있는 경로를 탐색해야 하며 안전지대에 도착하는 최단 경로의 거리를 계산해야합니다.   

고려해야할 점

• 우산을 쓰거나 버리는 시기는 우산이 있는 칸에 도착하는 때이다. 따라서 우산이 있는 칸에  도착하자 마자 새로운 우산을 쓰고 그 우산의 내구도가 하나 감소되어야 한다. 
• 우산의 개수는 최대 10개이다. (문제 조건으로 제시.)
• 우산의 내구도는 각 칸에 도착할 때마다 갱신해주어야 합니다. 따라서 플레이어의 체력에 빼고 더하는 것보다 우산과 플레이어의 체력을 분리하는 것이 구현하기 편합니다.

풀이 아이디어  

언뜻보면 가로 세로 격자를 모두 탐색하며 경로를 찾아야 하는 것 같지만 중요한 것은 우산, 안전지대로 이동하는 것입니다. 그 위치까지 최단 경로는 서로의 좌표 값을 비교하여 구할 수 있으므로 격자의 상태를 그래프로 전환하여 표현 할 수 있습니다. 

격자 모양의 배열에서 그래프로 전환

 이후 각 노드로 이동하는 경로를 DFS와 백트래킹을 활용하여 탐색하면 안전지대까지 최단 거리를 구할 수 있습니다. 

 

최적화

 모든 경로를 완전 탐색하는 코드로 구현하였다가 현재 이동거리가 안전지대까지의 최단 거리보다 작을 경우 이동하는 것으로 변경하여 연산 횟수를 감소시켰습니다. 

 

이전 코드 시간 788ms -> 코드 수정 후 168ms 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
	static int d;
	static int[][] point;
	static boolean[] visited;
	static int count;
	static int min;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		char[][] map = new char[n][n];
		count=0;
        // 맵 입력을 받음과 동시에 우산의 개수를 센다. 
		for(int i = 0; i < n; i++) {
			map[i] = br.readLine().toCharArray();
			for(int j = 0; j < n; j++) {
				if(map[i][j]=='U') count++;
			}
		}
		
		int[] s = new int[2]; // 시작점
		point = new int[count+1][2]; // 우산과 안전지대 위치 저장
		visited = new boolean[count+1]; // 방문 처리 배열 
		min = Integer.MAX_VALUE; // 최단 경로 저장 
		int index = 0; 
        // 각 지점 S, U, E 의 위치를 저장한다. 
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(map[i][j]=='S') 
					s = new int[] {i,j};
				if(map[i][j]=='U')
					point[index++] = new int[] {i,j};
				if(map[i][j]=='E')
					point[count] = new int[] {i,j};
			}
		}
		
        // DFS 탐색 
		dfs(0, h, 0, s[0], s[1]);
        // 만약 최단 경로가 처음에 할당해준 Integer.MAX_VALUE값 그대로 일 경우 다시 업데이트 
		if(min==Integer.MAX_VALUE)
			min = -1;
		System.out.print(min);
		
	}
	
    // DFS
	static void dfs(int distance, int h, int u, int x, int y) {
		// 현재 이동거리가 목적지까지 최단 경로보다 작아야 한다. 
        if(distance < min) {
        	// 목적지에 도착했을 경우 거리 저장 
			if(x == point[count][0] && y == point[count][1]) {
				min = distance;
			}else{
                // 방문하지 않은 지점들에 대해 DFS 탐색 
				for(int i = 0; i <= count; i++ ) {
					int temp = Math.abs(x - point[i][0])+Math.abs(y - point[i][1]);
					if(!visited[i]&&temp-1 < h+u) {
						int z = h; // 플레이어의 체력 
                        // 우산이 이동 중에 파손되거나 쓰고 있지 않을 때 체력 소모 
						if(u-temp+1 < 0) 
							z += (u-temp+1);
						visited[i] = true;
						dfs(distance+temp, z, d-1, point[i][0], point[i][1]);
						visited[i] = false;
					}
				}
			}
		}
	}
}