문제
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (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이다.
출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.
예제 입력 1
6 6 16
0 0 0 0 1 1
0 0 0 0 0 2
1 1 1 0 1 0
0 0 0 0 0 0
0 1 1 1 1 1
0 0 0 0 0 0예제 출력 1
10
주황색 선을 따라 검을 구하지 않고, 벽을 돌아가면 16시간만에 공주님에게 도착할 수 있다.
반면, 녹색선을 따라 "그람"을 구해, 벽을 부수고 공주님께 가면 10시간만에 도달할 수 있다.
예제 입력 2
3 4 100
0 0 0 0
1 1 1 1
0 0 2 0예제 출력 2
Fail문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ17836 {
static int N,M,T;
static int[][] map;
static boolean[][] visited;
static boolean[][] visitedItem;
static int[][] dir={{0,1},{0,-1},{1,0},{-1,0}};
static int min;
public static class Point{
int x,y,T;
boolean flag;
public Point(int x, int y,int T, boolean flag) {
this.x = x;
this.y = y;
this.T=T;
this.flag = flag;
}
}
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());
M=Integer.parseInt(st.nextToken());
T=Integer.parseInt(st.nextToken());
map=new int[N][M];
visited=new boolean[N][M];
visitedItem=new boolean[N][M];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<M;j++){
map[i][j]=Integer.parseInt(st.nextToken());
}
}
min=Integer.MAX_VALUE;
bfs();
if(min==Integer.MAX_VALUE){
System.out.println("Fail");
}
else{
System.out.println(min);
}
}
public static void bfs(){
Queue<Point> queue=new ArrayDeque<>();
queue.offer(new Point(0,0,0,false));
visited[0][0]=true;
while(!queue.isEmpty()){
Point p=queue.poll();
if(p.T>T) continue;
if(p.x==N-1 && p.y==M-1 && p.T<=T){
min=Math.min(min,p.T);
break;
}
for(int d=0;d<4;d++){
int nx=p.x+dir[d][0];
int ny=p.y+dir[d][1];
if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
if(p.flag){
if(!visitedItem[nx][ny]){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visitedItem[nx][ny]=true;
}
}
else if(!p.flag){
if(!visited[nx][ny] && map[nx][ny]!=1){
// 그람이 있는 위치인지
if(map[nx][ny]==2){
queue.offer(new Point(nx,ny,p.T+1,true));
visitedItem[nx][ny]=true;
}
else if(map[nx][ny]==0){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visited[nx][ny]=true;
}
}
}
}
}
}
}미로 탐색과 같은 문제처럼 BFS로 길을 찾는 알고리즘을 이용하고 아이템을 얻어 벽을 부술 수 있는 예외 사항을 처리하면 쉽게 풀 수 있는 문제였다.
이때, 방문 배열을 하나만 둘 것이 아니라 그람을 얻었을 때의 방문 배열을 따로 만들어 두어야하기 때문에 방문 배열을 두 개 이용해야한다.
고려할 점
- 아이템을 얻은 상태인지 확인하기 -> 벽을 부술 수 있음
- 아이템을 얻었을 때의 방문 배열과 아이템이 없을 때의 방문 배열을 따로 만들어줘야함
Point 클래스 만들기
public static class Point{
int x,y,T;
boolean flag;
public Point(int x, int y,int T, boolean flag) {
this.x = x;
this.y = y;
this.T=T;
this.flag = flag;
}
}Point 클래스에 좌표를 나타내는 x,y 값과 시간을 나타내는 T 값, 그리고 아이템을 얻었는지 확인하기 위한 flag boolean 변수를 넣어준다.
BFS 탐색
public static void bfs(){
Queue<Point> queue=new ArrayDeque<>();
queue.offer(new Point(0,0,0,false));
visited[0][0]=true;
while(!queue.isEmpty()){
Point p=queue.poll();
if(p.T>T) continue;
if(p.x==N-1 && p.y==M-1 && p.T<=T){
min=Math.min(min,p.T);
break;
}
for(int d=0;d<4;d++){
int nx=p.x+dir[d][0];
int ny=p.y+dir[d][1];
if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
if(p.flag){
if(!visitedItem[nx][ny]){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visitedItem[nx][ny]=true;
}
}
else if(!p.flag){
if(!visited[nx][ny] && map[nx][ny]!=1){
// 그람이 있는 위치인지
if(map[nx][ny]==2){
queue.offer(new Point(nx,ny,p.T+1,true));
visitedItem[nx][ny]=true;
}
else if(map[nx][ny]==0){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visited[nx][ny]=true;
}
}
}
}
}
}용사는 무조건 (0,0) 위치에서 시작하기 때문에 큐에도 (0,0) 위치값을 넣어준다.
처음에는 아이템을 가지고 있지 않은 상황이기 때문에 flag 또한 false로 지정해주고, 아이템이 없을때의 방문 배열을 체크해준다.
그리고 BFS 탐색을 진행하는데 큐에서 추출한 값에서 시간 값이 정해진 시간을 넘어가게 되면 더이상 탐색을 진행할 이유가 없기 때문에 다음 큐 값을 확인한다.
그리고 목표지점에 도달하게 되면 공주를 구출할 수 있으므로 min 값을 최소 시간으로 설정해주고 반복문을 빠져나온다.
상하좌우 방향으로 탐색을 해주면서 아이템을 가지고 있는 상황과 가지고 있지 않은 상황을 나누어준다.
아이템을 가진 상황
if(p.flag){
if(!visitedItem[nx][ny]){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visitedItem[nx][ny]=true;
}
}아이템을 가지고 있는 상황이라면 방문하지 않은 길이라면 벽이 있어도 뚫고 갈 수 있으므로 방문 배열만 체크한 뒤 큐에 값을 넣어준다.
이때, 아이템을 가지고 있을 때의 방문배열을 체크해야한다.
아이템이 없는 상황
else if(!p.flag){
if(!visited[nx][ny] && map[nx][ny]!=1){
// 그람이 있는 위치인지
if(map[nx][ny]==2){
queue.offer(new Point(nx,ny,p.T+1,true));
visitedItem[nx][ny]=true;
}
else if(map[nx][ny]==0){
queue.offer(new Point(nx,ny,p.T+1,p.flag));
visited[nx][ny]=true;
}
}
}아이템이 없다면 벽이 없는 공간만 이동이 가능하기 때문에 방문배열을 체크하고, 벽인지 아닌지도 체크해야한다.
이때, 검이 있는 공간도 방문 가능하기 때문에 검이 있는 공간에 방문하면 flag를 true로 넣어주고 방문 배열 또한 visitedItem 배열로 체크해준다.
그게 아니라면 flag는 그대로 false로 넣어주고 방문 배열 또한 visited 배열로 체크해준다.
