[BOJ] 미로탐색_2178

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
int map[1001][1001];
int check[1001][1001];
int cnt = 1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n, m;
int result = 0;
void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	check[x][y] = 1;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (map[nx][ny] == 1 && check[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					check[nx][ny] = check[x][y]+1;
					result = max(result, check[nx][ny]);
				}
			}
		}
	}
}


int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &map[i][j]);
			check[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && check[i][j] == 0)
				bfs(i, j);
		}
	}
	printf("%d\n", check[n-1][m-1]);
	return 0;
}

 

꽤 헤맸던 문제다.

먼저 map 배열을 입력받고 check 배열의 각 좌표에 도달할 수 있는 최소 거리를 계산한다.

근데 중간에 result를 작성했는데 result 수식 구문을 보면 check배열 nx,ny 좌표에 도달하는 거리랑 기존 result 값이랑 비교해서 큰 값을 선택하는 것으로 됐는데 이는 최소 경로를 구하는 알고리즘이 아닌 셈이다.

하지만 결과적으론, (0, 0) 좌표에서 (n-1, m-1) 좌표까지 도달해야하는 조건이 있으므로 

check[n-1][m-1] 값을 출력하면 끝