백준 2206 - 벽 부수고 이동하기(C++)

문제

N•M의 행렬로 표현되는 맵이 주어진다.

 

맵은 0과 1로 이루어져 있으며 '0'은 이동할 수 있는 곳 '1'은 벽을 의미한다.

 

(0, 0)부터 시작하여 (N-1, M-1)의 위치까지 이동하는 최단 거리를 구해야 한다.

 

이때 상하좌우로 이동할 수 있으며, 벽은 한 개까지 부수며 이동할 수 있다.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 1,000) (1 ≤ M ≤ 1,000)

 

다음 줄에는 N개의 줄에 M개의 숫자가 주어진다.

 

예제 입력

6 4
0100
1110
1000
0000
0111
0000

 

예제 출력

15

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'행렬', '최단 경로'를 통해 이 문제가 BFS를 이용하여 문제를 풀 수 있다는 것을 알 수 있다.

 

우선 최단 경로란 한 번 방문한 노드는 방문하지 않고 갈 수 있는 경로를 의미한다.

 

그렇기 때문에 보통 BFS 문제를 풀 때 방문 여부를 확인하는 cache 배열을 이용한다.

 

하지만 이 문제는 벽을 부실 수 있는 조건이 붙어있다. 즉, 다음의 두 가지 조건을 검사해야 한다.

 

• 벽을 부순적이 있는 상태에서 해당 위치를 방문했는가
  
  
• 벽을 부순적이 없는 상태에서 해당 위치를 방문했는가

이 두 가지를 검사하면서 BFS를 작성하면 오류가 날 일이 없다.

 

코드

#include <iostream>
#include <queue>
#include <string>

int board[1001][1001];
int N, M;
int cache[1001][1001][2];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

struct Point {
	int x;
	int y;
	int r;
	int crash;
};

bool isInBoard(int y, int x)
{
	return y >= 0 && y < N && x >= 0 && x < M;
}

bool isWall(int y, int x)
{
	return board[y][x];
}

bool isVisited(int y, int x, int crash)
{
	return cache[y][x][crash];
}

int bfs(void)
{
	std::queue<Point> pq;
	cache[0][0][0] = 1;
	cache[0][0][1] = 1;
	pq.push(Point({0, 0, 1, 0}));
	while (!pq.empty())
	{
		int currX = pq.front().x;
		int currY = pq.front().y;
		int currR = pq.front().r;
		bool currCrash = pq.front().crash;
		pq.pop();
		if (currX == M - 1 && currY == N - 1)
			return currR;
		for (int i = 0; i < 4; i++)
		{
			int nextX = currX + dx[i];
			int nextY = currY + dy[i];
			int nextR = currR + 1;
			if (isInBoard(nextY, nextX) && !isVisited(nextY, nextX, currCrash))
			{
				if (isWall(nextY, nextX))
				{
					if (!currCrash)
					{
						pq.push(Point({nextX, nextY, nextR, 1}));
						cache[nextY][nextX][1] = 1;
					}
				}
				else
				{
					pq.push(Point({nextX, nextY, nextR, currCrash}));
					cache[nextY][nextX][currCrash] = 1;
				}
			}
		}
	}
	return -1;
}

int main(void)
{
	std::cin >> N >> M;
	std::string str;
	for (int i = 0; i < N; i++)
	{
		std::cin >> str;
		for (int j = 0; j < M; j++)
			board[i][j] = str[j] - '0';
	}
	std::cout << bfs() << std::endl;
	return 0;
}

문제 출처

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기