백준 2206. 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

문제제목 : 벽 부수고 이동하기

문제난이도 : 골드4

문제유형 : BFS

 

문제

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. 목적지까지 최단경로를 구하기 위해서는 BFS 알고리즘을 사용한다.

2. 목적지까지 막힌 벽을 뚫을 수 있는 기회가 있으므로 큐에 저장할 때, 현재 정점까지 오면서 벽을 부셨는지, 안부셨는지에 대한 정보를 함께 저장해준다.

3. 하나의 정점에 도달할때는 벽을 부시고 온 경로와 벽을 안부시고 온 경로 2가지가 있다.

방문유무를 확인해야하는데, 방문유무 배열을 1개만 사용하면 벽을 부시고 정점에 도달한 경로와 벽을 안부시고 정점에 도달한 경로 두 개의 방문유무가 섞이므로 방문유무는 3차원배열을 이용한다.

4. 다음 정점으로 이동할 때,

   1. 지나갈 수 있는 길이고 이전에 벽을 부신적이 없음.

   2. 지나갈 수 있는 길이고 이전에 벽을 부신적이 있음.

   3. 지나갈 수 없는 길이고 이전에 벽을 부신적이 있음.

   4. 지나갈 수 없는 길이고 이전에 벽을 부신적이 없음.

이 4가지를 고려해야한다.

코드

package week4;

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

public class BOJ2206 {
	private static int N, M;
	private static int[][] map;
	private static boolean[][][] visited;
	private static int[][] data;
	private static int[] dx = {-1, 1, 0, 0};
	private static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] size = br.readLine().split(" ");
		N = Integer.parseInt(size[0]);
		M = Integer.parseInt(size[1]);
		
		map = new int[N][M];
		// visited[0][][] : 벽 부시고 온 경로 / visited[1][][] : 벽 안부시고 온 경로
		visited = new boolean[N][M][2];
		data = new int[N][M];
		
		// 맵 입력
		for (int i = 0; i < N; i++) {
			String[] input = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		// BFS 탐색
		System.out.println(BFS(0, 0));
	}
	
	public static int BFS(int x, int y) {
		Queue<Vertex> q = new LinkedList<>();
		q.add(new Vertex(x, y, 1));
		visited[x][y][1] = true;
		visited[x][y][1] = true;
		data[x][y]++;
		
		while (!q.isEmpty()) {
			Vertex now = q.poll();
			
			// 종점에 도착 시 거리 return
			if (now.x == N - 1 && now.y == M - 1) {
				return data[now.x][now.y]; 
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
					continue;
				}
				
				if (map[nx][ny] == 0 && !visited[nx][ny][now.chance]) {
					// 벽이 없고 방문하지않았다면
					q.add(new Vertex(nx, ny, now.chance));
					visited[nx][ny][now.chance] = true;
					data[nx][ny] = data[now.x][now.y] + 1;
				} else if (map[nx][ny] == 1 && now.chance == 1 && !visited[nx][ny][now.chance]) {
					 // 벽이고 벽을 부술 기회가 남았고 방문하지않았다면
					q.add(new Vertex(nx, ny, now.chance - 1));
					visited[nx][ny][now.chance] = true;
					data[nx][ny] = data[now.x][now.y] + 1;
				}
			}
		}
		return -1;	
	}
}

class Vertex {
	int x;
	int y;
	int chance; // 벽을 부술 기회 
	 
	public Vertex (int x, int y, int chance) {
		this.x = x;
		this.y = y;
		this.chance = chance;
	}
}

 

 

TC 

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

답 29

 

5 5
01100
01000
01110
01000
00010

답 9

 

 

---

문제를 풀면서 BFS를 이용하고 벽을 부술 수 있는 기회를 잘 사용하는 것까지 잘 짰는데,

visited 방문했는지 안했는지를 2개로 나눠야하는 것때문에 정말 골치아팠다.

블로그를 봐도 굉장히 헷갈렸는데 TC를 보고 하나하나 시뮬레이션을 해보니까 이해가 되었던 문제다.

그래도 이번 문제를 풀면서 BFS가 더 익숙해진 것 같다~