[백준_17836번] 공주님을 구해라!

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

17836번: 공주님을 구해라!

[문제]

 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

 

 성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

 우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

 

[입력 조건]

• 첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)
• 두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

 

[코드]

 

 

import java.util.*;

class Point_17836 {
	int x,y,count;
	boolean isGram; // 그람의 획득 여부를 체크하는 변수
	
	public Point_17836(int x, int y, int count, boolean isGram) {
		this.x=x;
		this.y=y;
		this.count=count;
		this.isGram=isGram;
	}
}

public class BaekJoon_17836 {
	static int[][] map;
	static boolean[][][] visited;
	static int n,m,t;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		t=sc.nextInt();
		
		map=new int[n][m];
		/*
		 * 그람이 있을 떄와 없을 때를 나눠 방문처리를 해주어야 하기 때문에 3차원의 배열을 사용한다.
		 * visited[n][m][0] : 그람이 없을 경우 
		 * visited[n][m][0] : 그람이 있을 경우
		 */
		visited=new boolean[n][m][2];
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				map[i][j]=sc.nextInt();
		
		int result=bfs(0,0);
		if(result==-1)
			System.out.println("Fail");
		else 
			System.out.println(result);
	}
	
	static int bfs(int x, int y) {
		Queue<Point_17836> q=new LinkedList<>();
		q.offer(new Point_17836(x,y,0,false)); // (0,0)에서 그람 없이 시작
		visited[x][y][0]=true;
		
		while(!q.isEmpty()) {
			Point_17836 now=q.poll();
			
			if(now.count>t) // 공주를 구할수 없는 경우 : t시간이 지남 
				break;
			
			if(now.x==n-1&&now.y==m-1) // 공주가 있는 칸에 도달한 경우
				return now.count;
			
			for(int i=0;i<4;i++) {
				int nx=now.x+dx[i];
				int ny=now.y+dy[i];
				
				if(nx>=0&&ny>=0&&nx<n&&ny<m) {
					if(!now.isGram) { // 그람을 획득하지 않은 경우 -> 방문한 곳과 벽이 있는 곳은 갈 수 없음
						if(!visited[nx][ny][0]&&map[nx][ny]==0) {
							visited[nx][ny][0]=true;
							q.offer(new Point_17836(nx,ny,now.count+1,false));
						}
						// 상,하,좌,우를 탐색하다 그람을 획득한 경우
						else if(!visited[nx][ny][0]&&map[nx][ny]==2) {
							visited[nx][ny][0]=true;
							q.offer(new Point_17836(nx,ny,now.count+1,true)); // isGram 변수를 true로 변겅
						}
						
					}
					else { // 그람을 획득한 경우 -> 벽 상관없이 방문 여부만 체크하면 됨
						if(!visited[nx][ny][1]) {
							visited[nx][ny][1]=true;
							q.offer(new Point_17836(nx,ny,now.count+1,true));
						}
					}
				}
			}
		}
		return -1;
	}
}

 

[고찰]

 이번 문제는 이전에 풀어봤던 다양한 최단거리 구하기 문제를 응용한다면 어렵지 않게 풀 수 있는 문제였다. 이 문제에서 중요한 포인트는 그람을 획득한 경우와 그렇지 않은 경우의 방문처리를 따로 해주어야 한다는 것이다. 따라서 3차원의 visited 배열을 사용해야 한다. 

 이후 최단거리를 구해야하므로 BFS 알고리즘을 사용하면 된다. 그람을 획득하지 않은 경우는 방문하지 않았으면서 벽이 없는 칸만 이동 가능하지만 그람을 획득했다면 벽의 유무를 고려하지 않아도 된다. 즉, 이동할 칸의 방문 여부만 체크하여 이동하면 된다. 

 

 이번 문제는 이전에 풀어봤던 최단거리 문제들의 유형들을 종합한 것 같은 문제여서 여러번 복습하기 좋은 문제라고 생각했다.