[백준/c++] BOJ 14923 - 미로 탈출

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

14923번: 미로 탈출

 

문제 설명

NxM 미로의 { Hx, Hy } 위치에서 시작하여, { Ex, Ey } 위치로 이동하려고 한다.

0은 길, 1은 벽을 나타낸다.

미로를 탈출하면서 단 한번, 벽을 뚫을 수 있을 때 미로를 탈출할 수 있는지 알아보고 가장 빠른 경로의 거리 D를 구한다.

인접한 칸으로 이동하는 데는 똑같이 시간 1이 들고, 벽을 부수는 데는 시간이 걸리지 않는다.

 

N, M (2 <= N, M <= 1000)

Hx, Hy, Ex, Ey (1 <= Hx , Hy, Ex, Ey <= 1000)

{ Hx, Hy } != { Ex, Ey }

 

해결

간단한 bfs 문제이다.

 

1. 시작 위치에서부터 시작하여 주변을 탐색하여 길을 찾아 간다.

 

2. 벽을 뚫었는지 확인하고 뚫을지 말지 결정한다.

 

3. 끝 위치를 만나면 이동 횟수를 리턴한다.

 

2번을 구현할 때 조심해야 하는데, visited 배열에서 벽을 뚫었을 때와 안 뚫었을 때를 차원을 나누어 확인해 주어야 한다.

또한 배열에서 { 0, 0 }의 위치가 문제에서는 { 1, 1 }로 나오므로 조심해야 한다.

 

bfs를 구현할 때 tuple을 원소로 { 0. 현재 위치의 x 좌표, 1. 현재 위치의 y 좌표, 2. 벽을 뚫었는지 여부, 3. 현재까지 이동 횟수 }를 저장해 주었다.

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int a, b;
pair<int, int> START, END;
int board[1001][1001], visited[2][1001][1001];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int range_over(int nx, int ny) {
	return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

int bfs() {
	queue<tuple<int, int, int, int>> q;
	q.push({ START.x - 1, START.y - 1, 0, 0 });
	visited[0][START.x - 1][START.y - 1] = 1;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = get<0>(cur) + dx[dir], ny = get<1>(cur) + dy[dir];
			if (range_over(nx, ny)) continue;
			if (visited[get<2>(cur)][nx][ny]) continue;
			if (board[nx][ny] && get<2>(cur)) continue;

			if (nx + 1 == END.x && ny + 1 == END.y)
				return get<3>(cur) + 1;

			if (board[nx][ny]) {
				q.push({ nx, ny, 1, get<3>(cur) + 1 });
				visited[1][nx][ny] = 1;
				continue;
			}

			q.push({ nx, ny, get<2>(cur), get<3>(cur) + 1 });
			visited[get<2>(cur)][nx][ny] = 1;
		}
	}
	return -1;
}

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

	cin >> n >> m;
	cin >> a >> b;
	START = make_pair(a, b);
	cin >> a >> b;
	END = make_pair(a, b);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> board[i][j];
	}

	int BFS = bfs();
	
	cout << BFS;
}