백준 2206 - 벽 부수고 이동하기

일반적인 BFS만 사용하다가 조금 흥미로운 문제라 작성하게 되었다.
문제는 이곳에서 풀어볼 수 있다.

1.문제 개요

격자 그래프의 최단거리를 BFS를 사용해서 구하는 문제이다.
여느 BFS와는 다른점이 있다면 벽을 1개까지 부수는게 가능하다.
일반적인 BFS처럼 풀면 좀처럼 쉼게 답이 나오지 않는다.
추가로 현재 블록을 부순 상태인지 추가로 확인해야 한다.

2.문제 풀이

1) 접근법

1. 일반 BFS처럼 방문 여부를 저장한다.
2. 추가로 현재 위치까지 도달하며 블록을 부쉈는지 판단할 수 있어야한다.
3. 벽을 부순 경로는 모든 경로로 방문한 곳을 방문하지 못한다.
4. 일반 경로는 벽을 부순 경로를 방문할 수 있다.

2) 나의 풀이

1. 벽을 부순이후의 방문 정보 저장
2. 다음의 조건을 확인한다.

• 좌표가 유효한지 확인

• 현재까지 벽을 부수지 않은 경우

  • 일반 경로로 방문O : 방문 불가
  • 일반 경로로 방문X :
    • 벽을 부순경로로 방문: 일반 경로로 방문한 것으로 대체
    • 어느 경로로도 방문X: 일반, 부순 경로 둘 다 방문 가능

• 벽을 이미 부순 경우

  • 모든 경로에서 방문 X : 벽이 없으면 방문

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
#define NMAX 1001
#define MMAX 1001

struct Pos
{
	int x;
	int y;
	int distance;
	bool _isBreak;

	bool operator==(Pos &operand)
	{
		return ((operand.x == x) && (operand.y == y));
	}

	bool operator!=(Pos &operand) { return !(*this == operand); }
};

int N, M;
bool isBreak = false;
vector<vector<int>> stage;
vector<vector<bool>> visited(NMAX, vector<bool>(MMAX, false));
vector<vector<bool>> breakvisited(NMAX, vector<bool>(MMAX, false));
Pos parent[NMAX][MMAX];
stack<Pos> route;

constexpr Pos START_POS = { 0, 0, 1, false };

bool CanGo(int x, int y, bool &_isBreak)
{
	// x y 좌표가 지정된 구역을 넘어서면 종료료
	if (x < 0 || x >= N)
		return false;
	if (y < 0 || y >= M)
		return false;

	// 0. 벽을 부수지 않은 경우
	if (!_isBreak)
	{
		// 0-1 벽을 부수지 않고 도달한 경로가 있다면 건너뜀
		if (visited[x][y] == true)
		{
			return false;
		}
		// 0-2 벽을 부수지 않고 도달한 경로가 없는 경우
		else if (visited[x][y] == false)
		{
			// 벽을 부숴서 이미 도달한 경우
			if (breakvisited[x][y] == true)
			{
				// 벽을 부수지 않고 도달할 수 있으면 벽을 부수지
				// 않는 것으로 교체
				if (stage[x][y] == 0)
				{
					visited[x][y] = true;
					Breakvisited[x][y] = false;
					_isBreak = false;
					return true;
				}
			}
			// 아무도 방문하지 않은 것
			else if (Breakvisited[x][y] == false)
			{
				// 막힌곳이면 벽을 부숨, 아니면 그냥 방문
				if (stage[x][y] == 1)
				{
					_isBreak = true;
					Breakvisited[x][y] = true;
					return true;
				}
				else
				{
					visited[x][y] = true;
					return true;
				}
			}
		}
	}
	// 1. 이미 벽을 부순 경우
	else if (_isBreak)
	{
		// 1-1 어떤 경우든 이미 도달했다면 건너뜀
		if (!visited[x][y] && !breakvisited[x][y] && stage[x][y] == 0)
		{
			Breakvisited[x][y] = true;
			return true;
		}
	}
	return false;
}

int BFS()
{
	queue<Pos> q;
	Pos EndPos { N - 1, M - 1 };

	bool found = false;
	// 시작점 추가
	q.push(START_POS);
	visited[0][0] = true;

	while (true)
	{
		if (q.size() == 0)
			break;

		Pos posHead = q.front();

		if (posHead == EndPos)
		{
			found = true;
			break;
		}
        
		q.pop();
        
		// R D L U 순으로 탐색
		int dx[4] = { 0, 1, 0, -1 };
		int dy[4] = { 1, 0, -1, 0 };

		for (int i = 0; i < 4; i++)
		{
			int nx = posHead.x + dx[i];
			int ny = posHead.y + dy[i];
			bool HeadBreak = posHead._isBreak;

			if (CanGo(nx, ny, HeadBreak))
			{
				q.push(Pos { nx, ny, posHead.distance + 1,
				    HeadBreak });
				parent[nx][ny] = posHead;
			}
		}
	}

	if (!found)
	{
		return -1;
	}

	return q.front().distance;
}

int main()
{
	ios_base ::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	stage.resize(N, vector<int>(M));

	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < M; j++)
		{
			stage[i][j] = s[j] - '0';
		}
	}
	int res = BFS();
}

변수와 여러번의 분기를 거치다보니 코드의 가독성이 떨어지는 문제가 있다.

3.다른 풀이를 참고한 개선

이 코드를 제출하려면 경로추적 부분을 지워야 합니다!
1. 2개의 visited변수를 사용하지 않고 3차원 배열 사용
2. 목표가 벽인지 아닌지로 분기
3. 경로추적

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
#define NMAX 1001
#define MMAX 1001

struct Pos
{
	int x;
	int y;
	int distance;
	bool _isBreak;

	bool operator==(Pos &operand)
	{
		return ((operand.x == x) && (operand.y == y));
	}

	bool operator!=(Pos &operand) { return !(*this == operand); }
};

int N, M;
int stage[NMAX][MMAX]; // 맵 정보
bool visited[NMAX][MMAX][2];
Pos parent[NMAX][MMAX][2];

bool CanGo(int x, int y, const Pos &head, bool &nb)
{
	if (x < 0 || x >= N || y < 0 || y >= M)
		return false;
	// 목표 지점이 벽이 아님
	if (stage[x][y] == 0 && !visited[x][y][head._isBreak])
	{
		// head._isBreak 상태로 방문한 적 없는 경우
		// (문을 부순 경로라면 문을 부순 경로상에서 방문한 적 있는지)
		visited[x][y][head._isBreak] = true;
		nb = head._isBreak;
		return true;
	}
	// 목표 지점이 벽임
	else if (stage[x][y] == 1 && !head._isBreak && !visited[x][y][1])
	{
		// 현재까지 벽을 부순적이 없고
		// 벽을 부순 경로로 이 위치를 방문한 적이 없는경우
		// 벽을 부숨
		visited[x][y][1] = true;
		nb = true;
		return true;
	}
	return false;
}

int BFS()
{
	queue<Pos> q;
	Pos EndPos { N - 1, M - 1 };
	Pos StartPos { 0, 0, 1, false };

	bool found = false;
	// 시작점 추가
	q.push(StartPos);
	visited[0][0][0] = true;

	while (true)
	{
		if (q.size() == 0)
			break;

		Pos posHead = q.front();
		q.pop();

		if (posHead == EndPos)
		{
			return posHead.distance;
		}

		// R D L U 순으로 탐색
		int dx[4] = { 0, 1, 0, -1 };
		int dy[4] = { 1, 0, -1, 0 };

		for (int i = 0; i < 4; i++)
		{
			int nx = posHead.x + dx[i];
			int ny = posHead.y + dy[i];
			bool nb;

			if (CanGo(nx, ny, posHead, nb))
			{
				parent[nx][ny][nb] = posHead;
				q.push(
				    Pos { nx, ny, posHead.distance + 1, nb });
			}
		}
	}

	return -1;
}

void PrintPath()
{
	stack<Pos> path;

	// 경로가 있을 때만 들어오니까 가능한 코드
	int b = visited[N - 1][M - 1] ? 0 : 1;

	// 도착점
	Pos currPos { N - 1, M - 1, 0, (bool)b };
	Pos StartPos { 0, 0, 1, false };

	while (currPos != StartPos)
	{
		path.push(currPos);
		currPos = parent[currPos.x][currPos.y][currPos._isBreak];
	}

	while (path.size() != 0)
	{
		cout << path.top().x << ", " << path.top().y << endl;
		path.pop();
	}
}

int main()
{
	ios_base ::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < M; j++)
		{
			stage[i][j] = s[j] - '0';
		}
	}
	int res = BFS();
	cout << res << "\n";

	if (res != -1)
	{
		PrintPath();
	}

	system("pause");
}

3. 소감

단순히 최단 경로를 찾는게 아니라 길을 개척하는점이 흥미롭다. 굳이 A*를 사용하지 않아도 되는 몬스터 AI들(턴제게임?) 등에 추가해보면 재미있을 것 같다.