[백준 1981] 배열에서 이동

분류 : 이분탐색, bfs

 

요구사항

(1,1) ~ (n,n)이동하는데 방문한 곳의 최소, 최대 값의 차이가 최소가 되도록 하기

 

풀이

최대, 최소값을 내가 정해준다음 bfs를 돌린다

start, end 포인트를 잡아주어, (n,n) 방문 할 수 있는 경우 최소를 구해야 하므로 start 증가

안될 경우 수의 차이를 증가 시켜 주어야 하므로 end 증가

 

#include <bits/stdc++.h>

using namespace std;
#define FOR(i,k) for(int i=0 ; i < k ; i++)
struct go {
	int x;
	int y;
};
int map1[220][220];
int n;
int maxv = 0;
int minv = 987654321;
vector<int> v;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int visit[220][220];

bool bfs(int low, int high) {
	queue<go> q;
	if (map1[0][0] >= low && map1[0][0] <= high)
		q.push({ 0,0 });
	else return false;
	memset(visit, 0, sizeof(visit));
	while (!q.empty()) {
		int r = q.front().x;
		int c = q.front().y;
		if (r == n - 1 && c == n - 1) return true;
		q.pop();
		FOR(i,4) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (map1[nr][nc] <= high && map1[nr][nc] >= low) {
				if (visit[nr][nc] == 0) {
					visit[nr][nc] = 1;
					q.push({ nr,nc });
				}
				
			}
		}
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for(int i=0 ; i < n ; i++)
		for (int j = 0 ; j < n; j++)
		{
			scanf("%d", &map1[i][j]);
			maxv = max(map1[i][j], maxv);
			minv = min(map1[i][j], minv);
		}
	for (int i = minv; i <= maxv; i++) {
		v.push_back(i);
	}

	int i = 0;
	int j = 0;
	int ans = 987654321;
	while (i < v.size() && j < v.size()) {
		minv = v[i];
		maxv = v[j];
		if (bfs(minv, maxv)) {
			if (maxv - minv == 0) {
				cout << "0" << endl; return 0;
			}
			else {	
				ans = min(ans,abs(maxv - minv));
				i++;
			}
		}
		else {
			j++;
		}
	}
	cout << ans << endl;
	
}