[BOJ] 2206 벽 부수고 이동하기

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

Note

벽을 한번 부술 수 있는 상태에서 0,0 에서 n,m 으로 갈 수 있는 최단 거리를 출력해주자.

과거에 비슷한 유형의 문제를 푼 적이 있다.
방문 체크를 할 때 벽을 부순 상태에 따라서 사용해야 하는 방문체크 변수가 다르다.
같은 위치에서 벽을 부수고 왔거나 부수지 않고 온 경우에 따라 도착거리가 달라 질 수 있기 때문이다.

그 부분을 분리해서 진행하면 생각보다 간단한 문제가 된다.

알고리즘

1. 가로, 세로 크기와, 맵 정보를 받는다.
2. 현재 위치에서 상,하,좌,우로 이동하는 경우를 판별한다.
   1. 다음 위치가 맵 범위에 속하는 경우 다음 위치가 벽인지 아닌지 판단한다.
   2. 벽이 아닌경우 현재까지 벽을 부순 기록이 있다면 벽을 부순 경우의 방문 체크 변수에 방문체크 후 큐에 넣는다.
   3. 벽을 부순 기록이 없는 경우 해당 방문 체크 변수에 방문 체크를 하고 큐에 넣는다.
   4. 벽인경우 현재 벽을 부순 기록이 없다면 기록이 있는 것으로 변경하고 방문 체크를 기록한다.
3. 목적지에 도착하는 경우 BFS를 중단하고 결과를 기록한다.
4. 출력

소스코드

#include <iostream>
using namespace std;

const int QMAX = 1000000;
const int BOARD_MAX = 1000;

struct Point {
	int dist;
	short x, y;
	bool wallBroken;

	Point() {};
	Point(short x, short y, int dist, bool w) : x(x), y(y), dist(dist), wallBroken(w) {};
};

struct Queue
{
	int top = 0;
	int rear = 0;
	Point data[QMAX];

	void push(Point p) {
		data[top++ % QMAX] = p;
	}

	Point pop() {
		return data[rear++ % QMAX];
	}

	bool isEmpty() {
		return top % QMAX == rear % QMAX;
	}
};

bool board[BOARD_MAX][BOARD_MAX];
short posX[4] = { 1, 0, -1, 0 };
short posY[4] = { 0, 1, 0, -1 };

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

	int row, col;
	int res = -1;
	Queue q;
	bool visited[BOARD_MAX][BOARD_MAX] = {};
	bool wallVisited[BOARD_MAX][BOARD_MAX] = {};

	cin >> col >> row;

	for (int i = 0; i < col; i++)
	{
		char line[BOARD_MAX + 1];
		cin >> line;
		for (int j = 0; j < row; j++)
			board[i][j] = line[j] - '0';
	}

	q.push(Point(0, 0, 1, false));
	visited[0][0] = true;

	while (!q.isEmpty()) {
		Point cur = q.pop();

		//cout << cur.dist << " : " << cur.x << " , " << cur.y << " - " << (cur.wallBroken ? "True" : "False") << endl;

		if (cur.x == col - 1 && cur.y == row - 1) {
			res = cur.dist;
			break;
		}

		for (int i = 0; i < 4; i++) {
			short nextX = cur.x + posX[i];
			short nextY = cur.y + posY[i];

			if (0 <= nextX && nextX < col && 0 <= nextY && nextY < row) {
				// Not wall
				if (!board[nextX][nextY]) {
					if (cur.wallBroken && !wallVisited[nextX][nextY]) {
						wallVisited[nextX][nextY] = true;
						q.push(Point(nextX, nextY, cur.dist + 1, cur.wallBroken));
					}
					else if (!cur.wallBroken && !visited[nextX][nextY]) {
						visited[nextX][nextY] = true;
						q.push(Point(nextX, nextY, cur.dist + 1, cur.wallBroken));
					}
				}
				// Wall
				else {
					if (!wallVisited[nextX][nextY] && !cur.wallBroken) {
						wallVisited[nextX][nextY] = true;
						q.push(Point(nextX, nextY, cur.dist + 1, true));
					}
				}
			}
		}
	}

	cout << res;

	return 0;
}

2019-04-21 18:15:42에 Tistory에서 작성되었습니다.