문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이

해당문제는 bfs로 풀면되는데, 상당히 고민을 많이 한 문제이다. 결국 다른 사람의 풀이를 보면서 이해한 뒤 풀었다. (링크)

x, y 좌표와 이동 거리, 벽을 부신 횟수를 저장하는 객체를 만들어야 한다. 또한 문제에서 벽은 단 한번만 부실수 있다는 조건이 존재한다.

즉. 벽을 안부시고 도착점까지 가는 경우와 벽을 한번 부시고 도착점까지 가는 경우를 생각해야 한다는 것이다.

대부분의 사람들은 3차원 배열을 사용하여 문제를 풀었다. visited 3차원 배열에서 visited[x][y][0]은 벽을 한번도 안부수고 탐색한 경우 이며, visited[x][y][1]은 벽을 한번 부수고 탐색을 진행하는 경우이다. 이부분에서 이해가 살짝 안되었다.

경우의 수를 정리하자면,

wall == 0 일때
0-1. 벽을 만나고 이전에 벽을 부신적이 없는 경우 -> 벽을 부수고 탐색(wall = 1로 바꿈)
0-2. 벽을 만나지 않았을 경우 그대로 방문처리 후 탐색

wall == 1일때,
1-1. 벽을 만났을 경우 이미 이전에 벽을 부셨기 때문에 탐색 종료 (코드상에선 이 경우를 제외하면 된다.)
1-2. 벽을 만나지 않은 경우 그대로 방문처리 후 탐색

이와같은 경우를 생각해서 풀면 결과를 출력할 수 있다.

소스

import java.util.*;

class Node {
	private int x;
	private int y;
	private int distance;
	// 벽을 부신 횟수
	private int wall;

	public Node(int x, int y, int distance, int wall) {
		this.x = x;
		this.y = y;
		this.distance = distance;
		this.wall = wall;
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getDistance() {
		return distance;
	}

	public int getWall() {
		return wall;
	}
}

public class Q2206 {
	public static int n, m;

	public static int[][] arr;
	public static boolean[][][] visited;

	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(x, y, 1, 0));
		visited[x][y][0] = true;
		visited[x][y][1] = true;

		int ans = Integer.MAX_VALUE;

		while (!q.isEmpty()) {
			Node node = q.poll();
			x = node.getX();
			y = node.getY();
			int distance = node.getDistance();
			int wall = node.getWall();

			if (x == n - 1 && y == m - 1) {
				ans = Math.min(ans, distance);
				break;
			}

			/*
			 * 경우의 수 wall == 0 일때 
			 * 0-1. 벽을 만났고 벽을 부신적이 없는 경우 벽을 부수고 wall = 1로 바꿈 
			 * 0-2. 벽을 만나지 않았을 때 그대로 방문처리 후 탐색
			 * 
			 * wall == 1 일때 (이전에 벽을 부순 경우) 
			 * 1-1. 벽을 만났을 때 , 이미 이전에 벽을 부셔서 탐색 종료 
			 * 1-2. 벽을 만나지 않았을 경우 그대로 방문처리 후 탐색
			 */

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

				// 범위 내에서
				if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
					// 이전에 벽을 부수지 않은 경우이면서 방문하지 않은 곳
					if (wall == 0 && !visited[nx][ny][0]) {
						// 벽인 경우 ( 0-1 상황)
						if (arr[nx][ny] == 1) {
							q.offer(new Node(nx, ny, distance + 1, wall + 1));
							visited[nx][ny][1] = true;
						}
						// 벽이 아닌 경우 ( 0-2 상황)
						else {
							q.offer(new Node(nx, ny, distance + 1, wall));
							visited[nx][ny][0] = true;
						}
					}
					// 이전에 벽을 부수고 방문하지 않은 곳
					else if (wall == 1 && !visited[nx][ny][1]) {
						// 벽이 아닌 경우만 체크( 1-2 상황)
						if (arr[nx][ny] == 0) {
							q.offer(new Node(nx, ny, distance + 1, wall));
							visited[nx][ny][1] = true;
						}
					}
				}
			}
		}

		if (ans == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(ans);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine();
		arr = new int[n][m];
		visited = new boolean[n][m][2];

		for (int i = 0; i < n; i++) {
			String str = sc.nextLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}

		// 시작점(0,0)부터 시작
		bfs(0, 0);

	}

}