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

이 포스트는 백준 사이트의 벽 부수고 이동하기 문제 풀이입니다.

문제

해결 과정

이 문제는 일반적인 탐색 문제와 다른 방문 기록을 사용해야 해결할 수 있습니다.

문제의 설명처럼 막혀있는 벽을 부수고 이동하면 최단거리가 갱신될 때, 벽 1개를 부술 수 있습니다.
여기서 2차원 배열의 방문 기록을 사용하면 현재 이동중인 칸이 벽을 부수고 왔는지 알 수 없습니다.

따라서 이 문제를 하결하고자
주어진 맵이 같은 모양으로 겹쳐 있는 3차원 배열을 구상했습니다.
현재 이동한 칸에서 벽과 만났을 때, (여러 겹의 맵에서)다른 층에서 이미 벽을 부수고 이동했다면
배열 값으로 true를 저장하도록 하였습니다.

그리고 이 과정 전체를 BFS 알고리즘을 사용해 구함으로서
문제를 해결할 수 있었습니다.

코드 구현

#include <iostream>
#include <queue>

#define SIZE 10

int N, M;
int** board;
int*** visited;

struct POS {
	int x, y, breaking_wall;
};

int DFS();


int main()
{
	std::cin >> N >> M;
	visited = new int** [N + 1];
	for (int i = 1; i <= N; ++i)
	{
		visited[i] = new int* [M + 1];
		for (int j = 1; j <= M; ++j)
		{
			visited[i][j] = new int[2] {0, 0};
		}
	}

	board = new int* [N + 1];
	for (int i = 1; i <= N; ++i) 
	{
		board[i] = new int[M + 1];
		for (int j = 1; j <= M; ++j)
		{
			scanf("%1d", &board[i][j]);
		}
	}

	printf("%d", DFS());
}

int DFS()
{
	int dx[4]{ 0, 0, -1, 1 };
	int dy[4]{ 1, -1, 0, 0 };
	std::queue<POS> q;
	q.push(POS{ 1, 1, 0 });
	visited[1][1][0] = 1;

	while (false == q.empty())
	{
		POS curr = q.front();
		q.pop();

		if (curr.x == M && curr.y == N)
			return visited[curr.y][curr.x][curr.breaking_wall];

		for (int di = 0; di < 4; ++di)
		{
			POS next{ curr.x + dx[di], curr.y + dy[di], curr.breaking_wall };

			if (next.y <= 0 || next.y > N || next.x <= 0 || next.x > M) continue;
			if (visited[next.y][next.x][curr.breaking_wall]) continue;

			if (0 == board[next.y][next.x])
			{
				visited[next.y][next.x][next.breaking_wall]
					= 1 + visited[curr.y][curr.x][curr.breaking_wall];
				q.push(POS{ next.x, next.y, curr.breaking_wall });
			}

			if (1 == board[next.y][next.x] && 0 == next.breaking_wall)
			{
				visited[next.y][next.x][1] = 1 + visited[curr.y][curr.x][curr.breaking_wall];
				next.breaking_wall = 1;

				q.push(next);
			}
		}
	}

	return -1;
}

실행 결과