백준 2206 (벽 부수고 이동하기)

문제

---

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

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

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

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

 

 

 

 

 

 

풀이

---

DFS (깊이 우선 탐색)을 통해서 풀 수 있지만 시간 초과가 나는 문제다.

 

BFS (너비 우선 탐색)을 이용해서 풀었다. 너비우선탐색을 사용하여 경우의 수를 줄였다.

기존의 너비우선탐색에선 해당위치를 방문했는지 안했는지를 boolean 배열로 값을 통해서 구한다.

하지만 이 문제같은 경우에는 int 배열로 값을 두어야 한다.

 

boolean 값으로 둘경우 

4 4
0000
1000
0011
0110

의 예시에서 정답은 7 이지만 상황에 따라 -1이 나오는 경우가 발생한다.

왜냐하면 이문제는 벽을 한번 뚫을 수 있는 조건이 있기 때문이다.

 

벽을 뚫었다는 횟수을 int 로 두어야한다. 그래야 더 적은 벽뚫은 횟 수를 가진 노드로 방문을 할경우에는 최신화를 시켜준뒤 방문을 할 수 있다.

하지만 boolean으로 둔경우는 한번 벽을 뚫고 추가된 노드에는 벽을 안뚫고 온 노드가 방문을 해도 방문을  할 수 없게 된다.

 

아래가 너비우선탐색 코드다.

static void bfs(int x, int y, int count) {
	
	Queue<node> queue = new LinkedList<node>();
	
	queue.add(new node(x, y, count, 0));
	visited[x][y] = 0;
		
		
	while(!queue.isEmpty()) {
		
		node now = queue.poll();
			
		if(now.x == n -1 && now.y == m - 1) {
			answer = now.dist;
			return;
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= m )
				continue;
			
			if(visited[nx][ny] <= now.cnt)
				continue;
			
			if(map[nx][ny] == 0) {
				visited[nx][ny] = now.cnt;
				queue.add(new node(nx, ny, now.dist + 1, now.cnt));
			}
			else {
				if(now.cnt < 1) {
					visited[nx][ny] = now.cnt + 1;
					queue.add(new node(nx, ny, now.dist + 1, now.cnt + 1));
				}
			}
		}
	}
}

 

해당 위치의 visited 값이 이전의 벽뚫은 횟수보다 적으면 최신화 시켜준다.

나머지는 기존의 너비우선탐색과 같다.

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class node{
		
		int dist, x, y;
		int cnt;
		
		public node(int x, int y, int dist, int cnt) {
			this.x = x;
			this.y = y;
			this.dist = dist;
			this.cnt = cnt;
		}
	}
	
	static int n, m;
	static int[][] map;
	static int[][] visited;
	static int answer;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n][m];
		visited = new int[n][m];
		for(int i = 0 ; i < n ; i++) {
			String[] line = bufferedReader.readLine().split("");
			for(int j = 0 ; j < m ; j++) {
				map[i][j] = Integer.parseInt(line[j]);
				visited[i][j] = Integer.MAX_VALUE;
			}
		}
		answer = Integer.MAX_VALUE;
		bfs(0, 0, 1);
		
		if(answer == Integer.MAX_VALUE)
			answer = -1;
		
		System.out.println(answer);
	}
	
	static void bfs(int x, int y, int count) {
		
		Queue<node> queue = new LinkedList<node>();
		
		queue.add(new node(x, y, count, 0));
		visited[x][y] = 0;
		
		
		while(!queue.isEmpty()) {
			
			node now = queue.poll();
			
			if(now.x == n -1 && now.y == m - 1) {
				answer = now.dist;
				return;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				if(nx < 0 || nx >= n || ny < 0 || ny >= m )
					continue;
				
				if(visited[nx][ny] <= now.cnt)
					continue;
				
				if(map[nx][ny] == 0) {
					visited[nx][ny] = now.cnt;
					queue.add(new node(nx, ny, now.dist + 1, now.cnt));
				}
				else {
					if(now.cnt < 1) {
						visited[nx][ny] = now.cnt + 1;
						queue.add(new node(nx, ny, now.dist + 1, now.cnt + 1));
					}
				}
			}
		}
		
	}
}