BOJ : 2206 벽 부수고 이동하기

[BOJ 2206(G4) 리뷰]

 

진짜 어려웠던 문제.. 첨에 머리싸매고 아무리 고민해도 풀이가 안떠올랐다.

벽이 있을때랑 없을때랑 해서 어찌저찌 해볼려했지만 도저히 풀리지 않았고

3D배열을 사용한다는 힌트를 봤을때 그제서야 조금씩 코딩을 할 수 있었다.

 

이 문제의 핵심은 '1.벽을 한번도 부수지 않고 목적지에 도착하는 경우' 와 '2.벽을 한번 부수고 목적지에 도착하는 경우' 로 나누어 계산해야한다. 따라서 거리를 기록하는 배열을 기존 2D배열에서 3D배열로 확장하여 진행 했다.

 

로직은 다음과 같다.

시작점 (1,1)에 방문표시를 하고 BFS를 시작한다.

상,하,좌,우 네가지 방향에 대해 방문을 실시한다. 만약 BFS를 진행중에 벽이 나타났다면 현재까지 벽을 부순적이 있는지 없는지 확인하고 벽을 부순적이 없으면 벽을 부순 후에 다시 방문을 진행한다. 벽을 부순적이 있다면 더 이상 벽을 부수지 못한다.

 

이렇게 반복문을 수행한 후에 목적지인 (n,m)에 거리가 기록되었다면 (1,1)에서 시작하여 (n,m)까지 도착을 했다는것이다. 만약 (n,m)값이 0이라면 도착하지 못한것이다.

 

목적지 값이 둘다 0이 아니라면 둘 중에 작은값이 시작점(1,1)에서 목적지(n,m)까지의 최소거리가 된다. 이를 출력하면 된다.

 

좀 어려웠으나 BFS의 동작원리를 다시한번 생각해 볼 수 있었다. 한번에 두가지 경우에 대해 탐색을 하는것도 익혔다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second
string board[1002];
int check[1002][1002][2]; 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1,  0, -1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}


	queue <pair<int,pair<int,int>>> Q;

	check[0][0][0] = 1;
	check[0][0][1] = 1;
	Q.push({ 0,{0,0} });
	while (!Q.empty())
	{
		auto cur = Q.front();
		int crash = cur.first;
		Q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.second.X + dx[dir];
			int ny = cur.second.Y + dy[dir];
			if (nx<0 || nx>=n || ny<0 || ny>=m) continue;
			if (check[nx][ny][crash]) continue; //이미 방문한적이 있음
			if (board[nx][ny] == '0')
			{
				check[nx][ny][crash] = check[cur.second.X][cur.second.Y][crash] + 1;
				Q.push({ crash,{nx,ny} });
			}
			else if (board[nx][ny] == '1' && crash == 0)
			{
				check[nx][ny][1] = check[cur.second.X][cur.second.Y][crash] + 1;
				Q.push({ 1,{nx,ny} });
			}
		}
	}

	int ans = 9999999;
	if (check[n - 1][m - 1][0] == 0 && check[n - 1][m - 1][1] == 0)
	{
		ans = -1;
	}
	else
	{
		if (check[n - 1][m - 1][0] == 0)
			check[n - 1][m - 1][0] = ans;
		if (check[n - 1][m - 1][1] == 0)
			check[n - 1][m - 1][1] = ans;
		ans = min(check[n - 1][m - 1][0], check[n - 1][m - 1][1]);
	}
	
	
	cout << ans;

}