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

문제 링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

bfs를 이용한 탐색 문제이다

 

기존의 탐색에서 벽을 한번 부수고 이동할 수 있다는 조건이 붙었기 때문에

 

구현하는데 어려움이 생겼다

---

이럴경우 각 좌표까지 최단거리를 두가지 상황으로 정리하면 쉽게 풀 수 있다

 

1. 벽을 뚫지 않고 격자까지 이동한 경우

 

2. 벽을 한번 뚫고 격자까지 이동한 경우

 

1번의 경우 벽이 없는 길로 1을 갱신하거나

 

벽을 뚫으면서 2의 최단거리를 갱신할 수 있지만

 

2번은 벽이 없는 길로 2번만 갱신할 수 있다.

---

bfs에 dp를 살짝 섞은 문제라고 볼 수 있다

 

#include <stdio.h>
#include <algorithm>
#include <queue>
#define n_ 1000 + 10
using namespace std;

char adj[n_][n_];
// x, y까지 최단경로를 저장하는 배열
// 여기서 마지막이 [x][y][0]이면 벽을 뚫은적 없이 이동했을 때 최단경로
// [x][y][1]이면 벽을 한번 뚫고 이동했을 대 최단경로
int dp[n_][n_][2];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int n, m;
// 변수 k는 x,y까지 올 때 벽을 뚫었는지 안뚫었는지 여부이다
// 안뚫었으면 0, 뚫었으면 1
typedef struct Node {
	int x, y, k;
}node;

queue<node> q;

void bfs() {
	// 시작은 0, 0에서 벽을 뚫지 않은 상태로
	q.push({ 0, 0, 0 });
	dp[0][0][0] = 1;

	while (!q.empty()) {
		node now = q.front();
		q.pop();

		int a = now.x;
		int b = now.y;
		int c = now.k;
		
		// 상하좌우 탐색
		for (int i = 0; i < 4; i++) {
			int nx = a + dx[i];
			int ny = b + dy[i];
			// 격자 밖이면 무시
			if (nx == -1 || nx == n || ny == -1 || ny == m) continue;

			// 식이 복잡하지만 adj[nx][ny]가 '1'일때와 '0'일때 따로 생각하면 편함
			// adj[nx][ny]가 '1', 벽일 경우 c가 1 증가. 벽이면 뚫고 이동할 것이기 때문
			// adj[nx][ny]가 '0', 벽이 아닐 경우 c는 그대로. 딱히 벽 안뚫고 그대로 이동
			int nk = adj[nx][ny] - '0' + c;

			// 벽을 이미 뚫었으면, 지금 뚫는 벽이 두번째라면 불가
			if (nk > 1)continue;	

			// 다음 격자까지 거리는 현재 위치까지 최단거리 + 1
			int nd = dp[a][b][c] + 1;

			if (nd < dp[nx][ny][nk]) {	// 기존 최단거리보다 작으면
				dp[nx][ny][nk] = nd;	// 업데이트 하고
				q.push({ nx, ny, nk });	// 큐에 push해서 bfs 한번 더

				// 새로 업데이트 된 노드이기 때문에 전에 탐색했더라도
				// 주위 격자에서 더 짧은 최단거리가 나올 가능성이 있음
			}
		}
	}
}

int main(void) {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		scanf("%s", adj[i]);

		// 모든 dp배열 값을 정수형 최대값으로 초기화해준다
		for (int j = 0; j < m; j++) {
			for (int l = 0; l < 2; l++) {
				dp[i][j][l] = 0x7fffffff;
			}
		}
	}

	bfs();	// bfs를 통해 dp배열 만들기 시작

	int res = 0x7fffffff;
	// res는 벽을 안부시고 도착한 최단거리와
	// 벽을 부시고 도착한 최단거리 중 작은 값이다
	for (int i = 0; i < 2; i++) {
		res = min(res, dp[n - 1][m - 1][i]);
	}

	if (res == 0x7fffffff) {	// 만약 그 값이 초기 설정값이면
		printf("-1\n");	 // 벽을 부셔도 도달할 수 없다
	}
	else {	// 도달할 수 있으면 최단경로 출력
		printf("%d\n", res);
	}

	return 0;
}