[백준] 2206 - 벽 부수고 이동하기

문제

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을 출력한다.

 

예제 입력

6 4
0100
1110
1000
0000
0111
0000

예제 출력

15

 

풀이 방법

1. 가중치가 없는 최단 거리를 구하는 것이므로 bfs를 이용

2. 벽을 한번만 부술 수 있는데 이것을 구분하기 위해 3차원배열 visited를 사용했다.

• 인접한 곳이 벽이 아닐 때 - 벽을 부수지 않고 탐색하는 경우
• 인접한 곳이 벽이 아닐 때 - 벽을 부수고 탐색하는 경우
• 인접한 곳이 벽일 때 - 벽을 부수지 않고 탐색하는 경우
• 인접한 곳이 벽일 때 - 벽을 부수고 탐색하는 경우(더이상 큐에 넣지 않는다.) 

 

파란색 화살표는 벽을 부수지 않고 가는 경우이고, 주황색 화살표는 벽을 부순 후 이동하는 경우이다.

오른쪽 그림을 보면 벽을 부순 주황색 화살표가 또 벽을 만나면 더 이상 갈 수 없다.

 

문제를 읽자마자 간단하게 생각했을때는 y좌표값, x좌표값, bfs의 깊이, 방문여부를 변수로 가지는 Node클래스로 Queue에 넣고 인접한 곳이 벽이라면 Node의 방문여부를 true로 바꾸어 주었는데

다시 생각해보니 그렇게 하면 처음 만나는 벽만 부술 수 있기 때문에 아래 같은 경우에 오른쪽 아래에 도착할 수 없다.

5 5
0 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
0 1 0 0 0

 

 

내 코드

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

public class Main_2206 {
	static int N, M, min=Integer.MAX_VALUE;
	static char[][] map;
	
	static class Node{
		int y, x, depth;
		boolean broken;
		
		public Node(int y, int x, int depth, boolean broken) {
			super();
			this.y = y;
			this.x = x;
			this.depth = depth;
			this.broken = broken;
		}
	}
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};

	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());
		map = new char[N][];
		
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		Queue<Node> queue = new LinkedList<>();
		boolean[][][] visited = new boolean[N][M][2];
		
		queue.offer(new Node(0,0,1,false));
		visited[0][0][0] = true;
		
		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			
			if(cur.y==N-1 && cur.x==M-1)
				min = Math.min(min, cur.depth);
			
			for (int d = 0; d < 4; d++) {
				int ny = cur.y + dy[d];
				int nx = cur.x + dx[d];
				
				if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
				
				if(map[ny][nx]=='0') {	//벽이 아닐 때
					if(!cur.broken && !visited[ny][nx][0]) { 	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,false));
						visited[ny][nx][0] = true;
					} 
					else if(cur.broken && !visited[ny][nx][1]) {	//지금까지 부순 벽이 있다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
				} else {	//벽일 때
					if(!cur.broken) {	//지금까지 부순 벽이 없다면
						queue.offer(new Node(ny,nx,cur.depth+1,true));
						visited[ny][nx][1] = true;
					}
					
				}
			}
		}

		if(min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
		
		br.close();

	}
}