[BaekJoon] 17836 공주님을 구해라! (Java)

1.  문제 링크

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

2.  문제

요약

• 용사는 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1, 1)로 들어갑니다.
• 성의 여러 군데 마법 벽을 세워놓았고, 용사는 현재 가지고 있는 무기로는 마법 벽을 통과할 수 없습니다.
• 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야 하는데 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌려 변하게 됩니다.
• 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 하고, 용사는 한 칸을 이동하는 데에 한 시간이 걸립니다.
• 용사는 상하좌우로 이동할 수 있습니다.
• 성에는 전설의 명검 "그람"이 숨어져있는데 용사가 그람을 구하면 마법의 벽이 있는 칸이라도, 벽을 부수고 그 공간으로 갈 수 있습니다.
• "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있으며 그람이 부술 수 있는 벽의 개수에는 제한이 없습니다.
• 용사가 공주님을 안전하게 구출할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 100보다 작거나 같은 성의 크기 N, M과 1보다 크거나 같고 10,000보다 작거나 같은 공주에게 걸린 저주의 제한 시간인 정수 T가 주어지며 두 번째 줄부터 N개의 줄에는 성의 구조를 나타내는 M개의 수가 주어집니다..
  • 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미합니다.
  • (1, 1)과 (N, M)은 0입니다.
• 출력: 첫 번째 줄에 용사가 T시간 이내에 공주에게 도달할 수 있다면 공주에게 도달할 수 있는 최단 시간을 출력하고, 용사가 공주를 T시간 이내에 구출할 수 없다면 "Fail"을 출력합니다.

3.  소스코드

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, M, T;
	static int[][] map;
	static boolean[][][] visited;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		T = scanner.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M][2];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < M; col++) map[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		int min = Integer.MAX_VALUE;
		Queue<Point> queue = new LinkedList<Point>();
		queue.add(new Point(0, 0, 0, false));
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			if(cur_point.time > T) {
				break;
			}
			if(cur_point.x == N - 1 && cur_point.y == M - 1) {
				min = Math.min(min, cur_point.time);
				break;
			}
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < N && cy >= 0 && cy < M) {
					if(map[cx][cy] == 0) {
						if(!cur_point.hasGram && !visited[cx][cy][0]) {
							queue.offer(new Point(cx, cy, cur_point.time + 1, cur_point.hasGram));
							visited[cx][cy][0] = true;
						} else if(cur_point.hasGram && !visited[cx][cy][1]) {
							queue.offer(new Point(cx, cy, cur_point.time + 1, cur_point.hasGram));
							visited[cx][cy][1] = true;
						}
					} else if(map[cx][cy] == 2 && !visited[cx][cy][0] && !visited[cx][cy][1]) {
						queue.offer(new Point(cx, cy, cur_point.time + 1, true));
						visited[cx][cy][0] = true;
						visited[cx][cy][1] = true;
					} else if(map[cx][cy] == 1) {
						if(cur_point.hasGram && !visited[cx][cy][1]) {							
							queue.offer(new Point(cx, cy, cur_point.time + 1, cur_point.hasGram));
							visited[cx][cy][1] = true;
						}
					}
				}
			}
		}
		System.out.println(min == Integer.MAX_VALUE ? "Fail" : min);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Point {
		int x, y, time;
		boolean hasGram;
		public Point(int x, int y, int time, boolean hasGram) {
			this.x = x;
			this.y = y;
			this.time = time;
			this.hasGram = hasGram;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• Point 클래스를 정의하는데 이 클래스는 위치 정보인 x, y와 해당 위치를 방문했을 때 지난 시간을 나타내는 time, 그람을 얻었는지를 나타내는 hasGram을 멤버 변수로 가집니다.
• BFS 탐색 시에 해당 위치를 방문하였는지 나타내는 3차원 배열 visited를 생성하는데 이는 다음을 의미합니다.
  • visited[x][y][0] : 그람을 아직 얻지 않았을 때 (x, y) 위치를 방문하였는지 나타냄
  • visited[x][y][1] : 그람을 얻은 이후에 (x, y) 위치를 방문하였는지 나타냄
• (1, 1) 위치부터 상하좌우 위치들을 각각 살펴보며 (N, M)까지 T 시간 내에 도달할 수 있는지 BFS를 통해 확인합니다.
• BFS 탐색 시에 방문할 위치들을 넣어놓을 Queue를 생성하고 (1, 1) 위치를 Point 클래스로 만들어 Queue에 넣습니다. 시작 위치이기 때문에 아직 시간이 지나지 않았고 그람을 얻지 않아 time은 0, hasGram은 false로 두고 시작합니다.
• Queue가 비워지기 전까지 Queue에 있는 Point 객체들을 하나씩 방문하면서 (N, M)에 시간 내에 도달할 수 있는지 확인합니다.
  • Queue에서 Point 객체를 하나 빼고 이를 cur_point에 넣습니다.
  • 만약 cur_point의 time이 T를 넘었다면 T시간 이내에 (N, M)에 도달하지 못했다는 뜻이므로 더이상 Queue에 있는 다른 위치들을 확인하지 않고 Fail을 출력합니다.
  • 만약 cur_point의 위치가 (N, M)이라면 T시간 이내에 (N, M)에 도달했기 때문에 공주에게 도달할 수 있는 최단 시간을 나타내는 변수 min의 값을 갱신하고 다른 위치들을 확인하지 않고 min값을 출력합니다.
  • 아직 T시간이 넘지 않았고 (N, M)에 도달하지 못했다면 cur_point의 상하좌우 위치를 각각 확인하며 해당 위치들을 방문할지를 결정합니다.
    • 해당 위치가 성 내에 위치할 때 해당 위치의 값이 0인지 1인지 2인지에 따라 취해야할 행동이 달라집니다.
      1. 해당 위치의 값이 0일 때
         • 현재 위치를 아직 방문하지 않았을 때, 현재 그람을 얻은 상태인지 아닌지에 따라 이후 행동이 달라지게 됩니다.
         1. 현재 그람을 얻지 않았고 아직 해당 위치를 방문하지 않은 경우(즉, cur_point의 hasGram이 false이고 해당 위치의 0번째 visited가 false일 때)
            • 해당 위치를 Queue에 넣고 해당 위치의 0번째 visited 값을 true로 변경합니다.
            • 해당 위치를 Queue에 넣을 때, 해당 위치의 위치값과 함께 cur_point의 time값에 1을 더한 값을 time으로, cur_point의 hasGram값을 hasGram으로 하여 Point 객체를 넣습니다.
         2. 현재 그람을 얻었고 아직 해당 위치를 방문하지 않은 경우(즉, cur_point의 hasGram이 true이고 해당 위치의 1번째 visited가 false일 때)
            • 해당 위치를 Queue에 넣고 해당 위치의 1번째 visited 값을 true로 변경합니다.
            • 해당 위치를 Queue에 넣을 때, 해당 위치의 위치값과 함께 cur_point의 time값에 1을 더한 값을 time으로, cur_point의 hasGram값을 hasGram으로 하여 Point 객체를 넣습니다.
      2. 해당 위치의 값이 1일 때
         • 해당 위치가 마법의 벽이기 때문에 그람을 얻지 않았다면 방문할 수 없는 위치이므로 그람을 얻었는지 확인해야 합니다.
         • 만약 그람을 얻은 상태이고 아직 해당 위치를 방문하지 않았다면(해당 위치의 1번쨰 visited 값이 false라면) Queue에 해당 위치를 Point 객체로 만들어 넣고 visited 값을 true로 변경합니다.
      3. 해당 위치의 값이 2일 때
         • 그람이 있는 곳이기 때문에 이 위치를 방문한 이후로는 그람을 얻은 상태가 됩니다.
         • 해당 위치를 아직 방문하지 않았다면 Queue에 해당 위치를 Point 객체로 만들어 넣는데, 이 때 그람을 얻었기 때문에 hasGram 값은 true로 넣습니다.
         • 해당 위치의 visited 값을 true로 변경합니다.