[백준/BFS] 2206: 벽 부수고 이동하기 - 자바

문제

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

2206번: 벽 부수고 이동하기

 

풀이

괴랄한 정답률이 왜 나왔는지 알 수 있는 문제..

처음에는 단순하게 한개의 벽을 부수고 BFS탐색하여 최단 경로를 구하려고 했는데

그렇게 쉽게를 문제가 나올리가 싶었다.

 

실마리를 찾지 못하다가. 질문글에서 다음 글을 보았다. 

4번 항목을 보면 여기까지 오면서 벽을 부순 적이 있는가 여부를 큐에 저장해서.... 를 보고 

벽을 깬 여부를 맵을 탐색하면서 같이 체크하면 되는 것이였다..

그래서 벽을 깬 여부를 3차원 배열에 넣고 체크하였더니 통과하였다.

 

코드 설명과 풀이는 아래에 첨부하였다.

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 Main {
	static int N, M;
	static int[][] map;
	static int ans = Integer.MAX_VALUE;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static class Location{
		int x, y, distance;
		boolean isWallBreak;
		public Location(int x, int y, int distance, boolean isWallBreak) {
			this.x = x;
			this.y = y;
			this.distance = distance;
			this.isWallBreak = isWallBreak;
		}
	}
	
	public static void main(String[] args) throws IOException {
		input();
		BFS(0,0);
		System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
	}
	
    /*
    # 이전에 벽을 부수지 않은 경우 wallBreak == false 
    1. 다음 탐색할 곳이 벽일 때 벽을 안 부쉈으므로(wallBreak = false)이므로 벽 부수고 이동한다 wallBreak = true로 바꿈
    2. 다음 탐색할 곳이 벽이 아닌 경우 방문처리하고 탐색을 계속 진행

    # 이전에 벽을 부쉈을 경우 wallBreak == true;
    1. 다음 탐색할 곳이 벽이라면 이미 벽을 부쉈으므로 해당 지점에서 탐색을 종료 -> 큐에 값을 넣지 않음
    2. 벽을 만나지 않은 경우, 방문 처리후 계속 탐색
    */
    
    
	public static void BFS(int x, int y) {
		boolean[][][] visited = new boolean[N][M][2];
		visited[x][y][0] = true; // 벽을 안깼을 때 방문체크
		visited[x][y][1] = true; // 벽을 깼을 때 방문체크
		
		Queue<Location> queue = new ArrayDeque<>();
		queue.add(new Location(x, y, 1, false));
	
		while(!queue.isEmpty()) {
			Location curLocation = queue.poll();
			int curX = curLocation.x;
			int curY = curLocation.y;
			int curDist = curLocation.distance;
			boolean curIsWallBreak = curLocation.isWallBreak;
			
			if(curX == N-1 && curY == M-1) {
				ans = Math.min(ans, curDist);
			}
			
			for (int d = 0; d < 4; d++) {
				int nx = curX + dx[d];
				int ny = curY + dy[d];

				if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
					// 이전까지 벽을 안깼다 && 방문하지 않음
					if (curIsWallBreak == false && !visited[nx][ny][0]) {
						if (map[nx][ny] == 1) { // 벽 일때
							queue.add(new Location(nx, ny, curDist + 1, true));
							visited[nx][ny][1] = true;
						} else { // 벽이 아니라면
							queue.add(new Location(nx, ny, curDist + 1, false));
							visited[nx][ny][0] = true;
						}
					// 이전까지 벽을 깼다 && 방문하지 않음. 
					} else if (curIsWallBreak == true && !visited[nx][ny][1]) {
						if (map[nx][ny] == 0) {
							queue.add(new Location(nx, ny, curDist + 1, true));
							visited[nx][ny][1] = true;
						}
					}
					
				}
			}
		}
	}
	
	public static void input() 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());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
		}
	}
}