[백준] 알고리즘 2178번 - 미로 탐색문제

문제

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

2178번: 미로 탐색

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n, m;
int arr[101][101];
int dist[101][101];
bool check[101][101];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
queue<pair<int, int>> qu;
void bfs(int x, int y) {
	qu.push({ x,y });
	check[x][y] = true;
	dist[x][y] = 1;
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx<0 || nx>n - 1 || ny<0 || nx>n - 1) continue;
			if (arr[nx][ny] == 1 && !check[nx][ny]) {
				qu.push({ nx,ny });
				check[nx][ny] = true;
				dist[nx][ny] = dist[ox][oy] + 1;
			}
		}
	}
}
int main() {
	//ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	bfs(0, 0);
	printf("%d", dist[n - 1][m - 1]);
}

해설

뭔가 문제에서 bfs나 dfs를 사용할 것 같은 뤼앙스를 풍기고있다.

최소거리, 최단거리를 구하기 위해서는 dfs를 이용할 수 없다.

왜냐하면 dfs는 운이 좋으면 경로의 최소로 가지만, 대부분의 경우 하나의 경로에 대해 깊게 파고들기에 어떤게 최단경로인지 알 수 없다.

이 경우 최소 최단의 말이 들어가면 bfs 부터 무지성으로 박아보자.

bfs는 경로에 하나하나 복제품을 배분하기에, 경로의 가중치가 1이라면 최단거리를 저장하면서 최종목적지까지 갈 수 있다.

bfs를 이용하면 저런식으로 가중치를 1씩더해서 영토를 확장해나간다고 생각하면된다.