[BOJ 14923 // C++] 미로 탈출

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14923번 문제인 미로 탈출이다.
문제는 아래 링크를 확인하자.

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

14923번: 미로 탈출

(행, 열, 벽을 뚫은 횟수)의 순서쌍을 하나의 노드로 생각하고, 주어진 미로의 인접한 변끼리 에지가 있는 그래프를 생각하자.

 

문제의 목적은 위에서 생각한 그래프에서 벽을 0번 뚫은 (Hx, Hy)에서 벽을 0번 뚫거나 1번 뚫은 (Ex, Ey)까지의 최단거리를 계산하는 것으로 볼 수 있다.

 

이 그래프의 에지의 가중치는 일정하므로, BFS를 이용해 최단거리를 구해낼 수 있다.

 

인접한 네 방향의 탐색을 구현할 때에는 아래의 코드와 같이 dx배열과 dy배열을 이용하면 편리하다.

 

아래는 제출한 소스코드이다.

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

struct node {
	int row, col, depth;
	node(int r, int c, int d) {
		this->row = r, this->col = c, this->depth = d;
	}
};

int R, C;
int sr, sc; // start
int er, ec; // end

int arr[1002][1002];
int dist[2][1002][1002];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs() {
	queue<node> que;
	dist[0][sr][sc] = 1;
	que.push(node(sr, sc, 0));

	while (!que.empty()) {
		node cur = que.front();
		que.pop();
		int r = cur.row, c = cur.col, d = cur.depth;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<1 || rr>R || cc<1 || cc>C) continue;
			if (arr[rr][cc] == 0) {
				if (dist[d][rr][cc]) continue;
				dist[d][rr][cc] = dist[d][r][c] + 1;
				que.push(node(rr, cc, d));
			}
			else {
				if (d) continue;
				if (dist[d + 1][rr][cc]) continue;
				dist[d + 1][rr][cc] = dist[d][r][c] + 1;
				que.push(node(rr, cc, d + 1));
			}
		}
	}
}

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

	cin >> R >> C >> sr >> sc >> er >> ec;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> arr[r][c];
		}
	}

	bfs();

	cout << min(dist[0][er][ec], dist[1][er][ec]) - 1;
}