2206번 - 벽 부수고 이동하기

1️⃣ BFS

 

✏️ 풀이 과정

BFS의 성질을 탐구하게 되는 문제입니다. 일반적으로 BFS를 통해 2차원 배열에서 거리를 구할 때는 큐의 사이즈만큼 for문을 돌려서 탐색 단계를 나누는 방법이 사용됩니다. 여기서는 방문 표시 배열을 2개로 나눠서 벽을 부순 경우와 부수지 않은 경우를 나누는 테크닉이 필요합니다.

 

왜 그렇게 되는가 정리해보자면 우선 탐색을 할 때 벽을 하나 부수기 위해서는 큐에 들어가는 원소에 벽을 부쉈는지 체크하는 불리언 값을 넣을 필요가 있습니다. 이를 통해서 이미 부순 경우에는 다시 벽을 부수지 않도록 하여 딱 한 번만 부수게 만들 수 있습니다. 이 때 발생하는 문제는 벽을 부수지 않은 루트를 이용해야 하는데 벽을 부순 루트가 더 어느 지점에 빠르게 도착해 있어 방문처리가 되어있기 때문에 부수지 않은 루트(정답 루트)가 중간에 끊겨버린다는 것입니다.

 

이 점을 해결하기 위해서 방문 배열을 두 개로 나누고 벽을 부수지 않았을 때는 양 쪽에 표시(어차피 가능한 최단경로가 되기 때문에) 부쉈을 때는 한 쪽에만 표시(부수지 않은 경로일 때는 확인하지 않음)하면 도중에 의도치 않게 막히는 경우 없이 BFS를 통해 최단경로를 구할 수 있습니다. 각 단계마다 카운트를 해주다가 도착 지점이 발견되면 탈출해서 카운트를 출력하면 문제가 해결됩니다. 종합해보면 BFS의 사이즈 사용 기법(거리 측정)과 방문 배열 나누기(속성이 다른 원소 분리) 기법을 모두 사용해서 문제를 해결했다고 할 수 있겠습니다.

 

⏱ 시간 복잡도

BFS의 시간 복잡도는 O(V+E)인데 이 경우 칸의 개수가 N*M이고 간선의 수도 이에 비례할 것이므로 O(NM)이 됩니다. 이 대략 1000000정도로 시간에는 큰 문제가 없으나 여기서는 공간 복잡도도 중요합니다. 아래 코드의 경우 딱 칸의 개수만큼인 O(NM)이지만 방문 표시를 큐에서 나온 이후에 해주는 방법을 이용하려 한다면 큐에 너무 많은 원소가 중복해서 들어가서 메모리 초과가 일어나게 됩니다. 

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
	
	static class Dozer {
		int r;
		int c;
		boolean used;
		
		public Dozer(int r, int c, boolean used) {
			this.r = r;
			this.c = c;
			this.used = used;
		}
	}
	
	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];
		String str;
		for(int i=0;i<N;i++) {
			str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		LinkedList<Dozer> q = new LinkedList<>();
		boolean[][] visited = new boolean[N][M];
		boolean[][] visited2 = new boolean[N][M];
		Dozer cur;
		q.offer(new Dozer(0, 0, false));
		visited[0][0] = true;
		int nr, nc, size, cnt = 0;
		int[] dr = {-1, 1, 0, 0};
		int[] dc = {0, 0, -1, 1};
		boolean found = false;
		loop:
		while(!q.isEmpty()) {
			size = q.size();
			cnt++;
			for(int t=0;t<size;t++) {
				cur = q.poll();
				if(cur.r == N-1 && cur.c == M-1) {
					found = true;
					break loop;
				}
				for(int i=0;i<4;i++) {
					nr = cur.r + dr[i];
					nc = cur.c + dc[i];
					if(nr<0 || nc<0 || nr>=N || nc>=M || visited[nr][nc]) {
						continue;
					}
					if(visited2[nr][nc] && cur.used) {
						continue;
					}
					if(map[nr][nc] == 1 && !cur.used) {
						q.offer(new Dozer(nr, nc, true));
					}
					if(map[nr][nc] == 0) {
						if(cur.used) {
							visited2[nr][nc] = true;
						} else {
							visited[nr][nc] = true;
							visited2[nr][nc] = true;
						}
						q.offer(new Dozer(nr, nc, cur.used));
					}
				}
			}
		}
		System.out.println(found ? cnt : -1);
		br.close();
	}
}