백준 2206, 벽 부수고 이동하기 - BFS

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

1. 아이디어

• 최단 거리 => BFS

• 벽을 부수지 않고 이동하는 경우, 벽을 부수고 이동하는 경우의 2가지 경우가 존재
  => 방문 확인 배열을 통해 2가지 경우를 구분하여, 서로 다른 경로 간에 간섭하지 못하도록 처리

  • 벽을 부수지 않고 탐색하는 경우의 방문 처리
  • 벽을 부수고 탐색하는 경우의 방문 처리
    
    

1) 다음 지점이 벽인 경우

• 현재 지점까지 벽을 부순 적 없으면, 부수고 이동

2) 다음 지점이 벽이 아닌 경우

• case 1) 현재 지점까지 벽을 부순 적 없고, 다음 지점을 아직 방문 안한 경우

• case 2) 현재 지점까지 벽을 부순 적 있고, 다음 지점을 아직 방문 안한 경우

오답 노트: 시간 초과
1) 전체 벽의 좌표들을 리스트에 저장
2) 벽 좌표 리스트에서 부술 벽 1개 선택 (k 개 벽이면, k 개 경우 존재)
3) 부술 벽 1개 선택 후, BFS 수행

• BFS 한 번 수행: O(V + E) = O(5V) (V = n x m)
• 전체 벽 개수가 k 이면, 총 시간 복잡도: O(5 x V x k)
  => 대충 k 가 n x m 이면, O(5 x n^2 x m^2)
  => n, m 최대값 대입: 5 x 10^6 x 10^6 >> 2억 (2초) => 시간 초과 !!
  => 전체 벽에서 1개 벽을 선택하여 부수는
  모든 경우의 수에 대해 BFS 를 수행하는 방법은 시간 초과 !!

2. 자료구조

• Queue<Point>, LinkedList<Point>: BFS
  => Point: 해당 지점 좌표, 해당 지점까지 이동한 거리, 해당 지점까지 이동하면서 벽 부순 여부
• boolean[][][]: 벽 부순 경우 / 안 부순 경우 방문 여부
  1) check[i][j][0]: [i, j] 지점까지 벽 부수지 않고 방문 여부
  2) check[i][j][1]: [i, j] 지점까지 벽 부수고 방문 여부
  
  

3차원 방문 확인 배열 대신, 2차원 방문 확인 배열 2개 사용해도 가능

• 본 문제에서는 [i, j] 지점에 대한 상태가 2가지(벽을 부순 경우, 부수지 않은 경우)이므로, boolean[][] check1, boolean[][] check2 처럼 2차원 방문 확인 배열 2개 사용해도 가능

3. 시간 복잡도

• 총 시간 복잡도: BFS 1번 수행
  => O(V + E) = O(5V) (V: n x m)
  => n, m 최대값 대입: 5 x 10^6 << 2억 (2초)

코드

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

class Point {
	public int y, x;
	public int distance;			// 현재 지점까지 이동한 거리
	public boolean destroyed;		// 현재 지점까지 이동하면서, 벽을 부순 여부

	public Point(int y, int x, int distance, boolean destroyed) {
		this.y = y;
		this.x = x;
		this.distance = distance;
		this.destroyed = destroyed;
	}
}

public class Main {
	static int n, m;			// n x m 행렬
	static char[][] map;
	static int minDistance = Integer.MAX_VALUE;	// 최단 거리

	static Queue<Point> queue = new LinkedList<>();
	static boolean[][][] check;		// 벽 부순 경우 / 안 부순 경우 방문 여부
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static void bfs() {
		while (!queue.isEmpty()) {
			Point current = queue.remove();

			if (current.y == n - 1 && current.x == m - 1) {	// 목표 지점
				minDistance = current.distance;
				return;
			}

			for (int i = 0; i < 4; i++) {
				int ny = current.y + dy[i];
				int nx = current.x + dx[i];

				// 다음 지점이 범위 밖인 경우
				if (ny < 0 || ny >= n || nx < 0 || nx >= m)
					continue;

				if (map[ny][nx] == '1') {	// 다음 지점이 벽인 경우
					// 현재 지점까지 벽을 부순 적 없고, 다음 지점을 아직 방문 안한 경우 => 부수고 이동
					if (!current.destroyed && !check[ny][nx][0]) {
						check[ny][nx][1] = true;
						queue.add(new Point(ny, nx, current.distance + 1, true));
					}
				}
				else {		// 다음 지점이 벽이 아닌 경우
					// 현재 지점까지 벽을 부순 적 없고, 다음 지점을 아직 방문 안한 경우
					if (!current.destroyed && !check[ny][nx][0]) {
						check[ny][nx][0] = true;
						queue.add(new Point(ny, nx, current.distance + 1, false));
					}
					// 현재 지점까지 벽을 부순 적 있고, 다음 지점을 아직 방문 안한 경우
					else if (current.destroyed && !check[ny][nx][1]) {
						check[ny][nx][1] = true;
						queue.add(new Point(ny, nx, current.distance + 1, true));
					}
				}
			}
		}
	}

	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());
		check = new boolean[n][m][2];
		map = new char[n][m];
		for (int i = 0 ; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < m; j++)
				map[i][j] = input.charAt(j);
		}

		check[0][0][0] = true;
		queue.add(new Point(0 ,0, 1, false));
		bfs();

		if (minDistance != Integer.MAX_VALUE)
			System.out.println(minDistance);
		else
			System.out.println(-1);
	}
}