백준 2206번 : 벽부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

 

 

 

 

 

문제

• N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳, 1은 벽이 있는 곳을 나타낸다.
• (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 최단 경로로 이동하려 한다.
  • 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸
• 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
• 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

 

 

 

 

풀이

상하좌우 인접한 칸으로 한 칸씩 이동했을 때의 최단 경로를 구하는 문제로, 한 칸씩 이동하며 사방탐색을 통해 모든 경우의 수에 대해 살피고 목표 지점에 도달했을시 탐색을 종료해야 한다. 따라서 큐를 이용한 BFS 알고리즘을 사용하여 문제를 풀었다.

 

전체적인 풀이는 다른 최단 경로를 구하는 문제와 같지만, '벽을 한 개 까지 부수고 이동할 수 있다'라는 조건이 붙으면서 풀이가 달라진다.

 

탐색을 할 때, 벽을 부쉈는지에 따라 이동이 달라지게 된다. 따라서 큐에 좌표 정보를 넣을 때, 행렬 좌표값, 이동 거리뿐만 아니라 지금까지 벽을 부순적이 있는지 정보를 저장할 필요가 있다. 따라서 좌표 정보를 담는 Point라는 객체에 boolean 형의 변수(hit)을 추가해줬다.

 

• 벽이 아님
  • 벽을 부순적이 있다 -> 그대로 탐색
  • 벽을 부순적이 없다 -> 그대로 탐색
• 벽이다
  • 벽을 부순적이 없다 -> 벽을 부수고 탐색
  • 벽을 부순적이 있다 -> 더이상 탐색 X

 

 

 

이대로 채점을 돌렸더니 틀렸다. 예제 입출력의 테스트케이스는 모두 통과하는데, 백준 문제 내 게시판에 있는 반례를 보니 틀린 원인을 찾을 수 있었다. (반례 : https://www.acmicpc.net/board/view/119335)

 

 

방문체크를 2차원의 boolean 배열로 해당 칸의 행렬 좌표값으로 체크를 해주고 있었는데, 이 부분에서 틀린 것을 발견할 수 있었다. 이전에 벽을 부수고 갔을 때, 방문체크가 되어 나중에 벽을 부수지 않고 해당 지점에 도달하게 되더라도 이미 방문체크가 되어 더이상 탐색을 할 수 없게 된다. 먼저 벽을 부수고 갔던 경로가 최단 거리일 수도 있지만, 후에 다른 지점에서 막히게 되어 도착하지 못하게 될 수 있다. 그러므로 벽을 부수지 않고 방문할 때의 가능성도 열어야 한다. 따라서 한 칸에 대해 벽을 부수지 않고 방문했을 때와 벽을 부수고 방문할 때로 나눠 방문체크를 해줘야 한다.

 

 

•  방문체크 : boolean[N][M][2]
  • [x][y][0] : 벽을 부수지 않고, 해당 지점을 방문했는가
  • [x][y][1] : 벽을 부수고, 해당 지점을 방문했는가

 

 

 

 

 

코드

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

public class Main {
	static int N, M;
	static int[][] graph;
	static boolean[][][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Point {
		int x;
		int y;
		int count;
		boolean hit;
		
		public Point(int x, int y, int count, boolean hit) {
			this.x = x;
			this.y = y;
			this.count = count;
			this.hit = hit;
		}
	}
	
	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());
		
		graph = new int[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1][2]; //0 : 벽 안부숨, 1: 벽 부숨
		
		for(int i = 1; i <= N; i++) {
			String row = br.readLine();
			
			for(int j = 1; j <= M; j++) {
				graph[i][j] = row.charAt(j - 1) - '0';
			}
		}
		
		int answer = bfs(1, 1);
		
		System.out.println(answer);
	}
	
	public static int bfs(int i, int j) {
		Queue<Point> queue = new LinkedList<>();
		
		queue.add(new Point(i, j, 1, false));
		visited[i][j][0] = true;
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			
			if(point.x == N && point.y == M) { // 종료 조건
				return point.count;
			}
			
			for(int d = 0; d < 4; d++) {
				int nx = point.x + dx[d];
				int ny = point.y + dy[d];
				
				if(1 <= nx && nx <= N && 1 <= ny && ny <= M) {
					if(graph[nx][ny] == 0) { //벽 아님
						if(!point.hit && !visited[nx][ny][0]) { //부순적 없음
							queue.add(new Point(nx, ny, point.count + 1, false));
							visited[nx][ny][0] = true;
						} else if(point.hit && !visited[nx][ny][1]) { //부순적 있음
							queue.add(new Point(nx, ny, point.count + 1, true));
							visited[nx][ny][1] = true;
						}
					}else if(graph[nx][ny] == 1 && !point.hit) { //벽 있음, 부순적 없음
						queue.add(new Point(nx, ny, point.count + 1, true)); //벽 부수기
						visited[nx][ny][1] = true;
					}
				}
			}
		}
		
		return -1;
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 방문체크를 할 때, 벽을 부쉈는지 안부쉈는지 나눠서 해야 한다.