BaekJoon 2206번: 벽 부수고 이동하기

풀이법

1) BFS를 사용해서 풀 수 있는 문제이지만, 벽을 하나 허물 수 있다는 점에서 BFS가 익숙치 않은 사람들에게는 어려움을 줄 수 있는 문제이다. 

2) 핵심은 이미 벽을 허물었는가를 확인하는 것 & visited 배열을 3차원으로 만드는 것이다.

3) visited 배열을 2차원으로 만들 경우 벽을 허물어서 지나간 곳과, 벽을 허물지 않았을 때 갈 수 있는 곳이 겹치게 되면, queue에 새로운 값을 push 할 수 없게 된다.

 

헷갈려 할만한 부분에 대해 주석을 자세히 달았으니, 이해를 기반한 공부에 도움이 되길 바란다. 

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

int n, m;
int arr[1001][1001];
int vx[4] = { 1,0,-1,0 };
int vy[4] = { 0,-1,0,1 };

int visited[1001][1001][2]; //벽 부신지 확인

int bfs()
{
	queue < pair<int, pair<int, int>>> q;
	q.push({ 1,{1,1 } }); //x=1, y=1, power=1(벽을 아직 안 허물었다)
	visited[1][1][1] = 1; //처음 칸도 센다.
	while (!q.empty())
	{
		int tx = q.front().first; //x좌표
		int ty = q.front().second.first;//y좌표
		int power = q.front().second.second; //벽 부실 수 있는지 여부
		q.pop();
		if (tx == n && ty == m)
		{
			return visited[n][m][power]; //반환 값
		}
		for (int i = 0; i < 4; i++)
		{
			int ux = tx + vx[i];
			int uy = ty + vy[i];
			if (ux<1 || ux>n || uy<1 || uy>m)
				continue;
			if (visited[ux][uy][power])
				continue;
			if (arr[ux][uy] == 0) //벽을 허물지 않고도 갈 수 있는 경우
			{
				visited[ux][uy][power] = visited[tx][ty][power]+1;
				q.push({ ux,{uy,power} });

			}
			if (power && arr[ux][uy]==1) //벽을 허무는 경우
			{
				visited[ux][uy][power-1] = visited[tx][ty][power]+1; 
				q.push({ ux,{uy,power-1} });//power값을 0으로 만들어 구분해준다.
			}
		}
	}
	return -1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		string a;
		cin >> a;
		for (int j = 0; j< a.size(); j++)
		{
			arr[i][j + 1] = a[j]-'0';
		}
	}
	cout << bfs();
}

주의사항)

3차원 배열

다른 방법을 이용하여 문제를 풀 수 있으나, visited를 3차원 배열로 사용함으로서 클린한 코드를 짤 수 있다. 

visited[x][y][power]에서 마지막 인자인 power는 1인 경우 벽을 허물 수 있는 것, 0인 경우 허물 수 없는 것을 의미한다. 벽을 허물지 않고서 지나갈 수 없는 해당 문제의 TC 1은 처음부터 벽을 허물지만, 만약 TC에 벽을 허물지 않고도 지나갈 수 있으나, 벽을 허물면 도착속도가 빨라지는 값이 들어오는 것을 고려하여 문제를 해결해야 한다.

 

배열을 3차원으로 해결하지 않은 경우 발생할 수 있는 문제점을 나타낸 좋은 Test Case가 있어 같이 첨부한다.

 

반례(Hidden TestCase) (출처: www.acmicpc.net/board/view/48468)

5 10
0000011000
1101011010
0000000010
1111111110
1111000000

정답: 14;
오답: -1 혹은 18;