2206 벽 부수고 이동하기

알고리즘 선택

1. 최단 경로로 이동

• BFS로 방문하는 모든 칸들은 시작점에서 최단 경로임을 보장

문제의 조건

• 한 개의 벽을 부수고 이동 가능
• 시작하는 칸, 끝나는 칸도 포함해서 센다.

문제 요구사항

• 맵이 주어졌을 때, 최단 경로 해석

직관적 해석

• 다음에 방문할 칸의 row, col 좌표를 알아야 함
• 다음에 방문할 칸의 방문 여부를 알아야 함
  • 벽이라면, 벽을 부순 여부도 알아야 함

---

구현사항

• 맵
  • row, col 좌표
  • 벽
• queue로 탐색
  • 다음에 방문할 칸의 row, col 좌표, 벽을 부순 여부를 알아야 하기 때문에 하나의 데이터로 관리

벽을 부쉈을 때와 아닌 경우의 최단 경로를 비교해야 하므로, 두 가지 값을 가지고 있어야 함

-> 배열의 차원을 하나 더 생성하여 각 경우를 저장

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N, M;
int field[1001][1001];
int bfs[2][1001][1001]; //벽 부순 상태, row, col
queue < pair<int, pair<int, int>>> q;
int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };
int Start()
{
	int nr, nc, cr, cc, block;
	q.push({ 0,{ 1, 1 } });
	bfs[0][1][1] = 1;
	while (!q.empty()) {
		pair<int, pair<int, int>> p = q.front();
		cr = p.second.first;
		cc = p.second.second;
		block = p.first;
		q.pop();
		//먼저 도달하면 그 경로가 최단 경로임
		if (cr == N && cc == M) {
			return bfs[block][cr][cc];
		}
		for (int i = 0; i < 4; i++) {
			nr = cr + dr[i];
			nc = cc + dc[i];
			if (nr < 1 || nc < 1 || nr > N || nc > M) {
				continue;
			}
			//다음에 방문할 칸이 벽이 아니고, 방문하지 않았다면
			if (field[nr][nc] == 0 && bfs[block][nr][nc] == 0) {
				bfs[block][nr][nc] = bfs[block][cr][cc] + 1;
				q.push({ block,{ nr, nc } });
			}
			//다음에 방문할 칸이 벽이고, 뚫어보지 않았다면 (방문 X)
			else if (field[nr][nc] == 1 && block == 0) {
				bfs[1][nr][nc] = bfs[0][cr][cc] + 1;
				q.push({ 1,{ nr, nc } });
			}
		}
	}
	return -1;
}
int main()
{
	memset(bfs, 0, sizeof(bfs));
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &field[i][j]);
		}
	}
	printf("%d\n", Start());
	return 0;
}