[백준 1981] 배열에서 이동

문제

www.acmicpc.net/problem/1981

1981번: 배열에서 이동

 

문제 풀이

 

지나갈 수 있는 최소 값과 최대 값을 투포인터로 관리하며 시작점부터 bfs를 통해 끝점까지 가는 경우에 최대 값 - 최소 값을 갱신해준다면 $O(N^2*200)$으로 시간내에 답을 구할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int n, g[101][101], ans, cr, cc, nr, nc;
bool vis[101][101];
vector<int> v;

bool cango(int l, int r) {
	memset(vis, 0, sizeof(vis));
	queue<pi> q;
	if (g[0][0] < v[l] || g[0][0] > v[r]) return 0;
	q.push({ 0,0 });
	vis[0][0] = 1;
	while (!q.empty()) {
		cr = q.front().first, cc = q.front().second;
		q.pop();
		if (cr == n - 1 && cc == n - 1) {
			ans = min(ans, v[r] - v[l]);
			return 1;
		}
		for (int i = 0; i < 4; i++) {
			nr = cr + dir[i][0], nc = cc + dir[i][1];
			if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
			if (!vis[nr][nc] && g[nr][nc] >= v[l] && g[nr][nc] <= v[r]) {
				q.push({ nr,nc });
				vis[nr][nc] = 1;
			}
		}
	}
	return 0;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> g[i][j];
			v.emplace_back(g[i][j]);
		}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int s = 0, e = 0;
	ans = v[v.size() - 1] - v[0];
	while (s < v.size()) {
		if (cango(s, e)) s++;
		else if (e < v.size()) e++;
		if (e == v.size()) break;
	}
	cout << ans;
}