[백준/BOJ] 백준 1981번 : 배열에서 이동

www.acmicpc.net/problem/1981

1981번: 배열에서 이동

(0,0)에서 (n-1,n-1)까지 이동하려고 하는 문제로 풀었다. 투 포인터(두 포인터)를 이용하여 left, right를 정하고 최솟값이 left, 최댓값이 right일때 (0,0)에서 (n-1,n-1)까지 이동할 수 있는지를 확인하여 이동할수 있을때중에서 right-left가 가장 작은값을 구한다

 

코드

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

int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//최소가 left, 최대가 right일때 (0,0)에서 (n-1,n-1)까지 이동할 수 있는지 확인
bool Search(int n, vector<vector<int>>& board, int left, int right)
{
	vector<vector<int>> discovered(n, vector<int>(n, 0));
	queue<pair<int, int>> q;

	if (board[0][0] < left || board[0][0] > right)
		return false;

	q.push(make_pair(0, 0));

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//(n-1,n-1)에 도달 했을때
		if (here.first == n - 1 && here.second == n - 1)
			return true;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discovered[there.first][there.second] == 0 && board[there.first][there.second] >= left && board[there.first][there.second] <= right)
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	return false;
}

// 투 포인터를 이용한다
int Solve(int n, vector<vector<int>>& board)
{
	int left = 0;
	int right = 0;
	int result = 987654321;

	while (1)
	{
		//최소가 left, 최대가 right일때 (0,0)에서 (n-1,n-1)까지 이동할 수 있는지 확인
		if (Search(n, board, left, right) == true)
		{
			result = min(result, right - left);
			left++;
		}

		else
			right++;

		if (right > 200)
			break;
	}

	return result;
}

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

	int n;
	vector<vector<int>> board(100, vector<int>(100, 0));
	int result;

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	result = Solve(n, board);

	cout << result;

	return 0;
}