BOJ - 17836 ) 공주님을 구해라!

---

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

17836번: 공주님을 구해라!

---

(1,1)에서 (N,M)이동할때 마검 그람을 얻으면 모든벽을 부수면서 진행할 수있는 문제이다. 

 

벽부수고 이동하기처럼, 방문처리를 따로 해줄 수 있지만, 모든벽을 부수고 (N,M)으로 간다는것은

 

현재 시점에서 (N,M)까지 유클리디안 거리를 의미한다.

 

따라서 그냥 BFS한 값과 비교하여 작은값을 선택해준다.

 

---

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

public class 공주님을구해라 {
	public static class node{
		int y,x,time;
		boolean isGet;
		public node(int y, int x, int time, boolean isGet) {
			this.y = y;
			this.time = time;
			this.x = x;
			this.isGet = isGet;
		}
	}
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int y = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int tt = Integer.parseInt(st.nextToken());
		
		boolean visit[][] = new boolean[y][x];
		int map[][] = new int[y][x];
		
		for(int i = 0 ; i < y; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < x ; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = -1;
		int answer_= -1;
		int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		
		ArrayDeque<node> dq = new ArrayDeque<>();
		dq.add(new node(0,0,0,false));
		visit[0][0] = true;
		int t = tt;
		while(!dq.isEmpty() && t>=0) {
			t--;
			int size = dq.size();
			while(size >0) {
				node now = dq.poll();
				if(now.isGet) {
					answer = now.time + (y -1 - now.y ) + (x-1  - now.x );
				}
				
				if(now.x == x-1 && now.y == y-1) {
					answer_ = now.time;
				}
				
				for(int i = 0 ; i < 4 ; i ++) {
					int ny = now.y+dir[i][0];
					int nx = now.x+dir[i][1];
					if(ny >=0 && nx >=0 && nx < x && ny < y) {
						if(!visit[ny][nx] && map[ny][nx] !=1) {
							if(map[ny][nx] ==2) {
								visit[ny][nx] = true;
								dq.addFirst(new node(ny,nx,now.time+1,true));
							} else if(map[ny][nx]==0) {
								visit[ny][nx] = true;
								dq.add(new node(ny,nx,now.time+1, false));
							}
						}
					}
				}
				size--;
			}
		}
		
		if(answer_ == -1 && answer >0 && tt >=answer ) {
			System.out.println(answer);
		} else if( answer_ > 0 && answer == -1) {
			System.out.println(answer_);
		} else if( answer_ > 0 && answer > 0) {
			answer = answer_ > answer ? answer : answer_; 
			System.out.println(answer);
		} else {
			System.out.println("Fail");
		}
		
	}
}

---