[백준] [2206] 벽 부수고 이동하기 (BFS) (JAVA)

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

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

예제 입력 1 복사

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 복사

15

예제 입력 2 복사

4 4
0111
1111
1111
1110

예제 출력 2 복사

-1

---

※ JAVA 코드 (벽 부수고 이동하기)

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

public class Main {
	static int N, M;
	
	// 맵 배열 선언
	static int[][] map;
	
	// 방문체크 배열 선언
	static boolean[][] visited;
	static boolean[][] isBreakVisited;
	// 상하좌우 이동경로
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	// (x, y) 좌표, 이동횟수, 벽 부숨 유무
	static class Node {
		int x, y, moveCnt;
		boolean isBreak;
		public Node(int x, int y, int moveCnt, boolean isBreak) {
			this.x = x;
			this.y = y;
			this.moveCnt = moveCnt;
			this.isBreak = isBreak;
		}
	}
	
	public static int BFS(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y, 1, false));
		visited[x][y] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			int nowX = now.x;
			int nowY = now.y;
			
			// 현재좌표가 (N, M)이라면 이동횟수 리턴
			if(nowX == N && nowY == M) {
				return now.moveCnt;
			}
			
			for(int i = 0; i < 4; i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];
				
				// 맵의 범위를 벗어나면 담지 않는다
				if(nextX <= 0 || nextY <= 0 || nextX > N || nextY > M) {
					continue;
				}
				
				// 이미 벽을 부순적이있고 다음 경로에 벽이 있다면 담지 않는다
				if(now.isBreak == true && map[nextX][nextY] == 1) {
					continue;
				}
				
				// 벽이 부순 적이 있고 다음 경로에 벽이 있다면
				if((now.isBreak == true && map[nextX][nextY] == 0) ||
				   (now.isBreak == false && map[nextX][nextY] == 1)) {
					
					if(isBreakVisited[nextX][nextY] == false) {
						q.offer(new Node(nextX, nextY, now.moveCnt + 1, true));
						isBreakVisited[nextX][nextY] = true;
					}
				}
				else {
					if(visited[nextX][nextY] == false) {
						q.offer(new Node(nextX, nextY, now.moveCnt + 1, false));
						visited[nextX][nextY] = true;
					}
				}
			}
			
		}
		
		return -1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 맵 크기 초기화
		map = new int[N+1][M+1];
		visited = new boolean[N+1][M+1];
		isBreakVisited = new boolean[N+1][M+1];
		
		// 맵 값 입력
		for(int i = 1; i <= N; i++) {
			String input = br.readLine();
			for(int j = 1; j <= M; j++) {
				map[i][j] = (int) input.charAt(j-1) - '0';
			}
		}
		
		int dap = BFS(1, 1);
		
		// 출력
		System.out.println(dap);
	}
}

---

※ 결과 (벽 부수고 이동하기)

---

※ 생각정리 (벽 부수고 이동하기)

벽 부수고 이동하기 문제는 처음 풀었을 때 21%에서 "틀렸습니다"를 만났다. 흠,, 분명 틀린게 없는거 같았는데 다시 한번 천천히 반례를 찾아나섰다.

문제는 벽을 1개라도 부수고 방문했던 좌표와 벽을 하나도 부수지 않고 방문했던 좌표의 방문체크배열이 중복 발생한 경우이다. 

 

사실 이 예제에서 벽을 한번만 부수고 9칸만 이용하여 목적지에 도착할 수 있다. 하지만 방문체크 배열을 하나만 두고 BFS알고리즘을 실행하면 첫번째 벽을 뚫는 (1, 2) 좌표에서 (2, 2) 좌표의 방문체크를 해버리기때문에 (2, 1) -> (2, 2) 로 이동하지 못한고 결국 벽 2개를 부수어야하는 것 처럼 만들어지기 때문에 -1을 리턴하게 된다.

이를 해결하기 위해서는 벽을 부수고이동하는 좌표의 방문체크 배열과 벽을 뚫지 않고 통로로만 이동하는 방문체크 배열 2개를 만들어서 방문체크를 해주어야 한다.

-새벽코딩-