1. 문제설명

NxM 행렬로 표현되는 맵이 주어진다.
0은 이동할 수 있는 곳, 1은 벽
(1, 1)에서 (N, M)까지 최단 경로를 구하라
- 만약 이동하는 도중에 한 개의 벽을 부수고 이동했을 때 경로가 더 짧아진다면,
- 벽을 한 개까지 부수고 이동해도 된다.
최단 경로 출력, 경로가 없다면 -1

2. 알고리즘 설계

BFS 문제로 최단 경로를 구한다.
벽을 부쉈을 때와 부수지 않았을 때를 같이 실행하면 된다.

3. 로직

첫번째 접근 방법 (시간초과)

모든 벽을 하나씩 부수고 그때마다 BFS

for (int i = 0; i < n; i++)
  for (int j = 0; j < m; j++) {
    cin >> map[i][j];
    if (map[i][j] == '1')
      wall.push_back({ i, j });
  }

for (pii cur : wall) {
  map[cur.first][cur.second] = '0';
  ans = min(ans, bfs(cur));
  map[cur.first][cur.second] = '1';
}

이동 중에 벽을 부수지 않는 경우와 벽을 한 개 부순 경우를 같이 큐에 담기

한 번에 두 경우를 모두 탐색할 수 있음!

for(int dir=0; dir<4; dir++) {
  int ny = cur.y + dy[dir];
  int nx = cur.x + dx[dir];

  if(map[ny][nx] == '1' && 벽 부수기 가능)  // 벽 부수고 이동
  if(map[ny][nx] == '0')  // 그냥 이동할 수 있다면
}

4. 전체 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
const int sz = 1001;
int visited[sz][sz][2] = { 0, };
char map[sz][sz];
int n, m;

typedef struct { int y, x, crush; }pos;

int bfs(void) 
{
	queue<pos> q;
	q.push({ 0,0,0 });
	visited[0][0][0] = 1;

	while (!q.empty()) {
		pos cur = q.front();
		q.pop();

		if (cur.y == n - 1 && cur.x == m - 1)
			return visited[cur.y][cur.x][cur.crush];

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.y + dy[dir];
			int nx = cur.x + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m)
				continue;
			if (visited[ny][nx][cur.crush])
				continue;

			if (map[ny][nx] == '1' && !cur.crush) {
				q.push({ ny, nx, 1 });
				visited[ny][nx][1] = visited[cur.y][cur.x][cur.crush] + 1;
			}
			if (map[ny][nx] == '0') {
				q.push({ ny, nx, cur.crush });
				visited[ny][nx][cur.crush] = visited[cur.y][cur.x][cur.crush] + 1;
			}
		}
	}
	return -1;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	cout << bfs();
}

5. 소감

처음에 벽 하나씩 부수고 탐색하는 방향으로 구현하였다.
- 생각해보니 맵의 대부분이 벽이라면?
- 거의 size의 제곱만큼 BFS를 돌게 될 것이다.
3차원 visited 배열을 이용
- 한 번의 이동으로 모든 조건을 검사할 수 있었다.
BFS 문제 대부분 2차원 맵이 주어졌다. (내가 푼 문제)
- 3차원 배열을 떠올리기까지 조금 오래 걸렸다..
- 어떻게 하면 시간을 줄일 수 있을까 굉장히 고민했던 거 같다.
이 문제 외에도 BFS 문제를 더 풀었지만, 구현 방식이 거의 동일해 포스팅하지 않았다.
BFS 관련 문제 유형
- 최단 경로
- 영역이 몇 개인지?
- 영역의 칸 수
- 무엇이 확산되는 조건 추가
  - 탈출까지 걸리는 시간
  - 최대 확산되기까지 걸리는 시간(1번이 1초)
문제 유형에서 상위 3개는 최단 경로 구하는 방식과 거의 다르지 않다.
확산 조건이 추가되면, queue의 size만큼 BFS를 해주면 된다.

BOJ 2206. 벽 부수고 이동하기

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감