[Java] 백준 2206번: 벽 부수고 이동하기

[문제 바로 가기] - 벽 부수고 이동하기

📌 유형 : BFS

💡 아이디어

첫번째 풀이

처음엔 간단한 BFS 문제라고 생각하여 Queue에서 {x 좌표, y 좌표, 지금까지 벽을 부순 횟수, 지금까지 이동한 칸의 개수}를 관리해주었다.

• 벽이 아닌 칸이라면 -> 벽 부순 횟수는 그대로, 이동한 칸 개수만 +1
• 벽이라면 벽 부순 횟수가 0일 경우에만 -> 벽 부순 횟수 +1, 이동한 칸 개수 +1

위와 같이 나눠서 해당 칸을 방문하는지 체크하는 2차원 배열을 사용하여 풀이했었다.

하지만 15%에서 틀렸습니다를 받았고

5 8
01000000
01010000
01010000
01010011
00010010

답이 20인 이 반례에서 -1이 나와, 내 코드는 이미 방문한 칸은 체크를 해버리기 때문에 어느 벽을 부수고 지나갔을 때 최적인지를 구하지 못한다고 생각했다.

두번째 풀이

그래서 DFS를 이용한다면 이미 방문했던 칸을 false 처리하여 최적의 해를 구할 수 있지 않을까 싶어 풀이를 바꿔보았다.

하지만 visited[dx][dy] = true와 false를 탐색하면 최대 100만개의 칸을 탐색할 뿐 아니라 벽을 부쉈는지/안 부쉈는지를 고려한다면 200만개가 된다.

그래서 당연하게도 시간 초과를 받고 다시 BFS 풀이로 돌아갔다.

세번째 풀이

첫번째 풀이에서 좌표만 체크해주었던 visited 배열을 [x좌표][y좌표][벽부순count]와 같이 3차원으로 체크했다.

• 벽이 없고, 현재 벽을 부순 상태(cur[2])에서 해당 좌표를 아직 방문하지 않았다면 -> 방문 체크 해주고 queue에 넣어준다.
• 벽이 있고, 아직 벽을 부순적 없고, 해당 좌표를 벽을 부순 상태(1)로 방문하지 않았다면 -> 방문 체크를 해주고 벽을 부순 count를 1로 하여 queue에 넣어준다.

그리고 이 문제에서 주의할 점은 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.가 있기 때문에 처음 Queue에 이동 거리를 넣어줄 때 1로 넣어주어야 한다!

---

풀이

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 {
	public static int[][] deltas = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] 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] = str.charAt(j) - '0';
			}
		}
		
		int answer = -1;
		
		Queue<int []> queue = new ArrayDeque<>();
		boolean[][][] visited = new boolean[N][M][2];
		
		// {x, y, 벽을 부순 횟수, 이동 거리}
		queue.offer(new int[] {0, 0, 0, 1});
		visited[0][0][0] = true;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			if (cur[0] == N - 1 && cur[1] == M - 1) {
				answer = cur[3];
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				int dx = cur[0] + deltas[i][0];
				int dy = cur[1] + deltas[i][1];
				
				if (dx < 0 || dy < 0 || dx >= N || dy >= M) continue;
				
				if (map[dx][dy] == 0 && !visited[dx][dy][cur[2]]) {
					visited[dx][dy][cur[2]] = true;
					queue.offer(new int[] {dx, dy, cur[2], cur[3] + 1});
				}
				
				if (map[dx][dy] == 1 && cur[2] == 0 && !visited[dx][dy][1]) {
					visited[dx][dy][1] = true;
					queue.offer(new int[] {dx, dy, 1, cur[3] + 1});
				}
			}			
		}
		
		System.out.println(answer);
	}
}