[백준/C++] 14923 미로 탈출

https://www.acmicpc.net/problem/14923

 

코드

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

#define MAX 1001
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);

typedef pair<int, int> pi;
int n, m, arr[MAX][MAX], hx, hy, ex, ey, ans = INT_MAX;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
bool visit[MAX][MAX][2];

void bfs() {
	queue<pair<pi, pi>> q;
	q.push({ {hx, hy}, {0, 0} });
	visit[hx][hy][0] = true;

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;

		int cnt = q.front().second.first;
		int use = q.front().second.second;

		q.pop();

		if (x == ex && y == ey) {
			ans = min(ans, cnt);
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int gx = x + dx[i];
			int gy = y + dy[i];

			if (gx >= 0 && gx < n && gy >= 0 && gy < m && !visit[gx][gy][use]) {
				if (arr[gx][gy] == 0 ) {
					q.push({ {gx, gy} , {cnt + 1, use} });
					visit[gx][gy][use] = true;
				}
				if (arr[gx][gy] == 1 && use == 0) {
					q.push({ {gx, gy}, {cnt + 1, 1} });
					visit[gx][gy][1] = true;
				}
			}
		}
	}
	
}
int main() {
	FASTIO;
	cin >> n >> m;
	cin >> hx >> hy;
	cin >> ex >> ey;
	hx--; hy--; ex--; ey--;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	bfs();

	if (ans == INT_MAX) cout << -1;
	else cout << ans;
	return 0;
}

설명

미로 정보를 입력받고, 홍익이의 현재 위치에서부터 bfs를 돌리면 된다. 큐에는 현재 좌표정보, 현재까지 이동한 거리, 지팡이 사용 횟수를 저장해주었다. 지팡이를 사용하지 않았다면 벽을 한 번 부술 수 있으므로 for 문 내에서 if문으로 경우를 나눠 처리했다.

 

느낀 점

지팡이 사용 횟수를 저장해주기 위해 3차원으로 방문 배열을 관리하면 된다! 입력되는 좌표가 1부터 시작하기 때문에 전부 1씩 감소시켜주고 시작했다.