백준 1981번 배열에서 이동

문제 링크입니다: https://www.acmicpc.net/problem/1981

1981번: 배열에서 이동

백준 2842번 집배원 한상덕(https://jaimemin.tistory.com/1279)과 유사하지만 조금 더 난이도가 쉬운 문제였습니다.

이차원 배열에 등장하는 모든 숫자들을 정렬된 상태로 각각 하나씩 가지고 있는 벡터 v가 이 문제의 핵심이였습니다.

low와 high를 초기에 0으로 두고 시뮬레이션을 통해 결과값을 계속 갱신해나가면 됩니다.

 

조건이 성립할 경우 low를 증가시키고 조건이 성립하지 않는 경우 high를 증가시킵니다.

조건이 성립하지 않고 더 이상 high를 증가시키지 못할 경우 반복문을 빠져나오면 되는 문제였습니다.

 

	#include <iostream>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	const int MAX = 100;
	const int INF = 987654321;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
	int N;
	int graph[MAX][MAX];
	bool visited[MAX][MAX];
	int result;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < N; j++)
	{
	cin >> graph[i][j];
	v.push_back(graph[i][j]);
	}
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	result = INF;
	int low = 0, high = 0;
	while (low < v.size())
	{
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	if (v[low] <= graph[0][0] && v[high] >= graph[0][0])
	{
	visited[0][0] = true;
	q.push({ 0, 0 });
	}
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
	{
	continue;
	}
	if (visited[nextY][nextX])
	{
	continue;
	}
	if (v[low] <= graph[nextY][nextX] && v[high] >= graph[nextY][nextX])
	{
	visited[nextY][nextX] = true;
	q.push({ nextY, nextX });
	}
	}
	}
	if (visited[N - 1][N - 1])
	{
	result = min(result, v[high] - v[low]);
	low++;
	}
	else if (high < v.size() - 1)
	{
	high++;
	}
	else
	{
	break;
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~