배열에서 이동

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	8617	2269	1476	24.449%

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다.

이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다.

이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다.

다음 n개의 줄에는 배열이 주어진다.

배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 – 최소)가 가장 작아질 때의 그 값을 출력한다.

예제 입력 1

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

예제 출력 1

2

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2006 6번

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO US Open 2003 Contest > Green 1번

• 문제를 번역한 사람: author5
• 데이터를 추가한 사람: kdk8361, yclock

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 이분 탐색
• 너비 우선 탐색

---

통과된 코드

범위를 확인할 때 이분탐색을 이용하여 시간 복잡도를 낮추어야 한다.

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

int _N, _Res = 1000;
int _inMax = -INT32_MAX, _inMin = INT32_MAX;
int _DxDy[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int _Map[101][101], _IsVisted[101][101];
int _End, _Start, _Mid;

queue<pair<int, int>> _BFSQueue;

bool BFS(int _Dif)
{
	for (int i = _inMin; i <= _inMax; i++) {
		for (int j = 1; j <= _N; j++)
			for (int k = 1; k <= _N; k++)
				_IsVisted[j][k] = true;

		// 해당 범위에 속한다면 방문체크  해제(탐색을 위함)  
		for (int j = 1; j <= _N; j++)
			for (int k = 1; k <= _N; k++)
				if (i <= _Map[j][k] && _Map[j][k] <= i + _Dif)
					_IsVisted[j][k] = false;
		// 도착지점이 성립할 수 없는 경우
		if (i > _Map[_N][_N] || _Map[_N][_N] > i + _Dif) 
			continue;
		while (!_BFSQueue.empty())
			_BFSQueue.pop();
		_BFSQueue.push(make_pair(1, 1));
		while (!_BFSQueue.empty()) {
			pair<int, int> _Pos = _BFSQueue.front();
			_BFSQueue.pop();
			if (_IsVisted[_Pos.first][_Pos.second]) continue;
			_IsVisted[_Pos.first][_Pos.second] = true;
			if (_Pos.first == _N && _Pos.second == _N)
				return true;
			int _dx, _dy;
			for (int i = 0; i < 4; i++) {
				_dx = _Pos.first + _DxDy[i][0];
				_dy = _Pos.second + _DxDy[i][1];
				if (_dx > _N || _dy > _N || _dx <= 0 || _dy <= 0) continue;
				_BFSQueue.push(make_pair(_dx, _dy));
			}
		}
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	int _in;
	for (int i = 1; i <= _N; i++)
		for (int j = 1; j <= _N; j++) {
			cin >> _in;
			_Map[i][j] = _in;
			_inMax = max(_in, _inMax);
			_inMin = min(_in, _inMin);
		}

	_End = _inMax - _inMin;
	_Start = 0;
	while (_Start <= _End) {
		_Mid = (_End + _Start) / 2;
		if (BFS(_Mid)) _End = _Mid - 1;
		else _Start = _Mid + 1;
	}
	cout << _End + 1;
	return 0;
}