백준 - 벽 부수고 이동하기 (2206) [C++]

이 문제는 bfs를 이용해서 풀었다.

 

visited 배열에 이미 벽을 하나 부쉈는지에 대한 여부 정보를 추가하면 쉽게 풀 수 있다.

결론적으로 가중치가 1인, 즉 단순히 이동한 거리에 대한 최소를 구하면 되므로 가장 먼저 (N, M) 에 도착한 것을 리턴해주어도 정답이 나올 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define MAX 1000
#define INF 1000000000
#define NOT_DESTROY 0
#define DESTROY 1

int N, M;
int matrix[MAX + 1][MAX + 1];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int dist[MAX + 1][MAX + 1][2];

bool inRange(int y, int x) {
	if (1 <= y && y <= N && 1 <= x && x <= M) {
		return true;
	}

	return false;
}

struct Node {
	int y;
	int x;
	int destroy;
};

int bfs(int startY, int startX) {
	dist[startY][startX][NOT_DESTROY] = 1;
	queue<Node> q;
	q.push({ startY, startX, NOT_DESTROY });

	while (!q.empty()) {
		Node present = q.front();
		q.pop();

		int y = present.y;
		int x = present.x;
		int destroy = present.destroy;
		
		if (y == N && x == M) {
			return dist[y][x][destroy];
		}

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

			if (!inRange(ny, nx)) {
				continue;
			}

			if (destroy == NOT_DESTROY) {
				if (matrix[ny][nx] == 0 && dist[ny][nx][destroy] > dist[y][x][destroy] + 1) {
					dist[ny][nx][destroy] = dist[y][x][destroy] + 1;
					q.push({ ny, nx, destroy });
				} else if (matrix[ny][nx] == 1 && dist[ny][nx][DESTROY] > dist[y][x][destroy] + 1) {
					dist[ny][nx][DESTROY] = dist[y][x][destroy] + 1;
					q.push({ ny,nx,DESTROY });
				}
			} else if (destroy == DESTROY) {
				if (matrix[ny][nx] == 0 && dist[ny][nx][destroy] > dist[y][x][destroy] + 1) {
					dist[ny][nx][destroy] = dist[y][x][destroy] + 1;
					q.push({ ny,nx,destroy });
				}
			}
		}
	}
	return -1;
}

void init() {
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++) {
			for (int i = 0; i < 2; i++) {
				dist[y][x][i] = INF;
			}
		}
	}
}

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

	cin >> N >> M;
	init();

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++) {
			char c;
			cin >> c;
			matrix[y][x] = c - '0';
		}
	}

	int result = bfs(1, 1);
	cout << result << '\n';
	
	return 0;
}