Life Engineering
[BOJ 17836] 공주님을 구해라! (Java) 본문
https://www.acmicpc.net/problem/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 배열에 방문 표시를 해준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 11054] 가장 긴 바이토닉 부분 수열 (Java) (0) | 2022.03.08 |
---|---|
[BOJ 1043] 거짓말 (Java) (0) | 2022.03.08 |
[프로그래머스] 방문 길이 (Java) (0) | 2022.03.03 |
[BOJ 1744] 수 묶기 (Java) (0) | 2022.03.03 |
[BOJ 17825] 주사위 윷놀이 (Java) (0) | 2022.03.02 |