백준 14923 - 미로 탈출(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14923

14923번: 미로 탈출

BFS문제 였습니다. 일반 BFS문제와는 다르게 벽을 부숴야함으로, check배열을 3차원으로 만들어 벽을 부셨는지의 여부를 확인해주면 되는 문제였습니다.

문제 조건

출력 예시

벽을 부셨는지의 여부를 확인해야하는게 포인트 였습니다.

check[X][Y][Z] 배열을 선언해, Z부분에서 벽을 부셨는지의 여부를 확인했습니다.

이 부분을 제외하면 다른 BFS 문제와 같은 방법으로 풀면 되는 문제였습니다.

 

문제 접근 방법

1. 4방향으로 탐색하는 도중, 벽이 있고 이전에 벽을 부순적이 없다면, 해당 벽을 부수고 들어갑니다.

2. 4방향으로 탐색하는 도중, 벽이 없다면, 해당 방향으로 탐색을 계속합니다.

3. 도착점에 도달하면 이동 횟수를 return 합니다.

4. 탐색이 끝났는데도 도착하지 못했다면 -1을 return 합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int map[1001][1001];
int check[1001][1001][2];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
pair<int, int> start, finish;

typedef struct qu {
	int x;
	int y;
	int cnt;
}qu;

int bfs() {
	queue<qu> q;
	q.push({ start.first, start.second, 0 });
	check[start.first][start.second][0] = 1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
		if (x == finish.first && y == finish.second) {
			return check[x][y][cnt];
		}
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (cnt == 0) {
					if (map[xx][yy] == 1) {
						if (check[xx][yy][cnt] == 0) {
							check[xx][yy][cnt+1] = check[x][y][cnt] + 1;
							q.push({ xx,yy,cnt + 1});
						}
					}
					else {
						if (check[xx][yy][cnt] == 0) {
							check[xx][yy][cnt] = check[x][y][cnt] + 1;
							q.push({ xx,yy,cnt });
						}
					}
				}
				else {
					if (check[xx][yy][cnt] == 0 && map[xx][yy] == 0) {
						check[xx][yy][cnt] = check[x][y][cnt] + 1;
						q.push({ xx,yy,cnt });
					}
				} 
			}
		}
	}
	return -1;
}

void solve() {
	int ans = bfs();
	if (ans == -1) cout << ans;
	else cout << ans - 1;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	cin >> start.first >> start.second;
	cin >> finish.first >> finish.second;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!