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

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

17836번: 공주님을 구해라!

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_BOJ_17836 {
	static class Pos{
		int r, c, cnt;
		boolean isGram;
		public Pos(int r, int c, int cnt, boolean isGram) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.isGram=isGram;
		}
		
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M, T;
	static int[][] map;
	static boolean[][][] check;
	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];
		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());
			}
		}
		check=new boolean[N][M][2];
		int answer=bfs(0,0);
		if (answer==-1 || answer>T) {
			System.out.println("Fail");
		}
		else {
			System.out.println(answer);
		}
		
	}
	private static int bfs(int r, int c) {
		Queue<Pos> q=new LinkedList<>();
		q.add(new Pos(r,c,0,false));
		check[r][c][0]=true;
		while (!q.isEmpty()) {
			Pos p=q.poll();
			if (p.r==N-1 && p.c==M-1) {
				return p.cnt;
			}
			if (map[p.r][p.c]==2) {	//검을 찾았을 때 탐색 case 시작
				p.isGram=true;
			}
			for (int i=0; i<4; i++) {
				int nr=p.r+dr[i];
				int nc=p.c+dc[i];
				if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
				if (!p.isGram) {
					if (map[nr][nc]!=1 && !check[nr][nc][0]) {
						check[nr][nc][0]=true;
						q.add(new Pos(nr,nc,p.cnt+1,p.isGram));
					}
				}
				else {
					if (!check[nr][nc][1]) {
						check[nr][nc][1]=true;
						q.add(new Pos(nr,nc,p.cnt+1,p.isGram));
					}
				}
				
			}
		}
		return -1;
	}
	
	
		

}

이 문제의 포인트는=> check 배열을 3차원으로 만들어서 검을 찾았을 경우/검을 아직 못 찾은 상태 2가지로 나눠주는 것이다.

 

탐색을 시작할 위치가 검의 위치라면, 그때부터 검을 찾은 상태라고 정의하고 check 배열에 방문 표시를 해준다.