Baekjoon 2206 벽 부수고 이동하기

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

소스결과 16516 KB / 52 ms

출처 Baekjoon

언어 C++ 17

분류 BFS

 

설명

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

 

과거에 비슷한 유형의 문제를 푼 적이 있다.

방문 체크를 할 때 벽을 부순 상태에 따라서 사용해야 하는 방문체크 변수가 다르다.

같은 위치에서 벽을 부수고 왔거나 부수지 않고 온 경우에 따라 도착거리가 달라 질 수 있기 때문이다.

 

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

 

알고리즘

1. 가로, 세로 크기와, 맵 정보를 받는다.

2. 현재 위치에서 상,하,좌,우로 이동하는 경우를 판별한다.

 2-1. 다음 위치가 맵 범위에 속하는 경우 다음 위치가 벽인지 아닌지 판단한다.

 2-2. 벽이 아닌경우 현재까지 벽을 부순 기록이 있다면 벽을 부순 경우의 방문 체크 변수에 방문체크 후 큐에 넣는다.

 2-3. 벽을 부순 기록이 없는 경우 해당 방문 체크 변수에 방문 체크를 하고 큐에 넣는다.

 2-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;
}