BFS & DFS - 백준 2178번 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

IDEA

(0,0) 에서 (N,M)까지 장애물을 피해 갈 수 있는 최단 거리를 묻는 문제다.

내 머릿속은 최단거리 = BFS 때문에 BFS로 풀었다.

최단거리를 묻는 문제 같은 경우 따로 VISITED를 사용하지 않고 MAP자체에 거리를 업데이트해준다. 

맨 처음 시작점인 0,0을 큐에 넣어준다.

큐의 front를 기준으로 상하좌우 4방향의 map값을 확인한다. 

map이 0이라면 갈 수 없고, 1이 아니라면 이미 지나온 곳이라는 뜻이다.

그렇기에 새로운 좌표 nx,ny가 범위 내에 있으면서 map값이 1이면 큐에 넣을 수 있다. 

이때 nx,ny까지의 거리는 x,y까지의 거리 + 1 이므로 map 값을 업데이트시켜준다. 

문제에서 무조건 n.m으로 이동할 수 있다고 했기때문에 bfs의 반복문이 끝난 후 map[n-1][m-1]값을 반환해준다. 

 

코드

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

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int n, m;
int arr[100][100] = {0};
queue<pair<int, int>>q;

bool check(int x, int y) {
	if (-1 < x && x < n && -1 < y && y < m) return true;
	return false;
}

int bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (check(nx, ny) && arr[nx][ny] == 1) {
				arr[nx][ny] = arr[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
	return arr[n-1][m-1];
}

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	q.push({ 0,0 });
	printf("%d" , bfs());
}