백준 14923 - (Java) 미로 탈출

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

14923번: 미로 탈출

1. 유형

BFS

 

2. 문제 접근

BFS 유형 중에서 3차원 배열을 사용하는 문제입니다.

 

위의 예시를 들어봅시다.

 

만약 3차원 방문배열이 아닌, 2차원 방문 배열을 한다고 가정합시다.

 

초록색 루트로 (1,1)을 탐색해버리고 방문체크를 합니다. 그러고 나서 빨간색 루트로 (1,1)을 탐색할 때는 이미 방문 체크가 되어있으니, (1,1)에 접근할 수 없습니다. 그러면 결국 (2,1)까지 도달하지 못해서 -1을 출력해 줄 것입니다.

 

위 같은 반례가 존재해서 방문 배열에 지팡이를 썼는지 안 썼는지 기록을 해줘야 합니다.

 

visit [row][col][지팡이 남은 횟수] 형식으로 방문 배열을 만들고. 기본 BFS를 돌려주면 쉽게 정답이 나옵니다.

 

참고로 위와 비슷한 유형으로

1600 - 말이되고픈 원숭이

2206 - 벽부수고 이동하기

등이 있습니다.

 

3. 코드

import java.util.*;
import java.io.*;

public class Main {
	static int N,M,map[][];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N=stoi(st.nextToken());
		M=stoi(st.nextToken());
		st = new StringTokenizer(in.readLine());
		int startr=stoi(st.nextToken())-1;
		int startc=stoi(st.nextToken())-1;
		st = new StringTokenizer(in.readLine());
		int endr=stoi(st.nextToken())-1;
		int endc=stoi(st.nextToken())-1;
		map=new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j]=stoi(st.nextToken());
			}
		}
		bfs(startr,startc,endr,endc);
	}
	static void bfs(int r, int c, int endR, int endC) {
		int d[][]= {{-1,0},{0,1},{1,0},{0,-1}};
		Queue<int[]> q=new LinkedList<>();
		boolean visit[][][] = new boolean[N][M][2];
		q.add(new int[] {r,c,1,0});
		visit[r][c][1]=true;
		int answer=-1;
		while(!q.isEmpty()) {
			int cur[]=q.poll();
			int curR=cur[0];
			int curC=cur[1];
			int cnt=cur[2];
			if(curR==endR && curC==endC) {
				answer=cur[3];
				break;
			}
			for(int k=0;k<4;k++	) {
				int nr=curR+d[k][0];
				int nc=curC+d[k][1];
				if(nr<0||nr>=N||nc<0||nc>=M) continue;
				if(cnt>0 && !visit[nr][nc][cnt-1] && map[nr][nc]==1) {
					visit[nr][nc][cnt-1]=true;
					q.add(new int[]{nr,nc,cnt-1, cur[3]+1});
				}
				if(!visit[nr][nc][cnt] && map[nr][nc]==0) {
					visit[nr][nc][cnt]=true;
					q.add(new int[]{nr,nc,cnt, cur[3]+1});
				}
			}
		}
		System.out.println(answer);
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}