[BOJ]1981번: 배열에서 이동 (c++)

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

1981번: 배열에서 이동

 

이분탐색 + bfs

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct pos {
	int x, y;
};

const int MAX = 200;
int N;
int dr_x[] = { 0, 1, 0, -1 };
int dr_y[] = { 1, 0, -1, 0 };
int min_val = MAX;
int max_val = 0;

bool bfs(vector<vector<int>>& board, int mn, int mx)
{
	// [0][0]위치의 요소가 하한, 상한 요소값 범위 밖이면 false
	if (board[0][0] < mn || board[0][0] > mx)
	{
		return false;
	}

	queue<pos> q;
	q.push({ 0, 0 });
	vector<vector<bool>> visit(N, vector<bool>(N));
	visit[0][0] = true;

	while (!q.empty())
	{
		pos p = q.front();
		q.pop();

		// 주어진 하한, 상한 요소값으로 [N - 1][N - 1]로 도달할 수 있으면 true
		if (p.x == N - 1 && p.y == N - 1)
		{
			return true;
		}

		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			// 범위 밖이거나 방문한 적 있으면 continue
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || visit[nx][ny])
			{
				continue;
			}

			// 다음 위치의 요소가 하한, 상한 요소값 범위 밖이면 continue
			if (board[nx][ny] < mn || board[nx][ny] > mx)
			{
				continue;
			}

			visit[nx][ny] = true;
			q.push({ nx, ny });
		}

	}
	// [N - 1][N - 1]로 도달할 수 없으면 false
	return false;
}

bool check_gap_possible(vector<vector<int>>& board, int gap)
{
	/*
		요소값의 범위가 [최소요소, 최소요소 + gap]일 때,
		[0][0] ~ [N - 1][N - 1] 도달할 수 있는지 확인
	*/
	for (int i = min_val; i + gap <= max_val; ++i)
	{
		if (bfs(board, i, i + gap))
		{
			return true;
		}
	}
	return false;
}

// 갭(최대요소 - 최소요소)의 최소값을 이분탐색으로 찾기
int binary_search_gap(vector<vector<int>>& board)
{
	int left = 0;
	int right = max_val - min_val;
	int min_gap = right;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		// mid를 갭으로 했을 때, [0][0] ~ [N - 1][N - 1]까지 도달할 수 있는지 확인
		if (check_gap_possible(board, mid))
		{
			min_gap = min(mid, min_gap);
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return min_gap;
}

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

	// 입력
	cin >> N;
	vector<vector<int>> board(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> board[i][j];

			// 최소 요소, 최대 요소 구하기
			min_val = min(board[i][j], min_val);
			max_val = max(board[i][j], max_val);
		}
	}

	// 갭(최대요소 - 최소요소)의 최소값을 이분탐색으로 찾기
	cout << binary_search_gap(board);

	return 0;
}

 

 

시행착오를 많이 겪은 문제였다.

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다.
이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.
이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

첫째 줄에 n(2≤n≤100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다.
배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

 

이 문제의 특징은 주어진 수의 범위가 크지 않다는 것이다. 

그래서 처음부터 이 문제를 보고 이분탐색으로 풀어야 한다는 생각을 하지 못했다.

 

 

하지만 이문제의 또다른 중요 특징은 지나간 위치를 다시 지나갈 수 있다는 것이다. 

만약 이 문제를 dfs + 갭 최소값 메모이제이션으로 풀이할 경우 다음의 딜레마에 빠지게 된다.

// 다음 조건문에 어떤 식이 들어가야 할까?
if ( ?? )
{
    min_gap[nx][ny] = t_right - t_left;
    dfs(board, min_gap, t_left, t_right, {nx, ny});
}

1. min_gap[nx][ny] > t_right - t_left

2. min_gap[nx][ny] >= t_right - t_left

 

1번으로 풀 경우, 가능한 정답을 찾지 못할 수 있다. 갭이 같은 경로를 무시하게 되기 때문이다.

2번으로 풀 경우, 무한루프에 빠지게 될 수 있다. 갭이 같은 위치를 무한히 방문하게 되기 때문이다.

그럼 2번에 visit bool배열을 더해 한번 방문한 곳을 다시 방문하지 못하게 하면?

이번에는 가능할 수 있던 경로를 찾지 못하게 될 수가 있다.

 

 

그래서 이분탐색으로 풀어야 한다. 

엄밀하게는 이분탐색 + 브루트 포스이다. 

풀이 순서는 다음과 같다. 

1. 이분탐색 : 가능한 갭(mid)을 찾는다. (0 <= 갭 <= 200)

2. 브루트포스 : [최소요소, 최대요소] 범위 제한의 갭이 mid인 모든 범위에 대해서 bfs탐색을 시도한다.

3. bfs : 주어진 범위 내에서 [0][0] ~ [N - 1][N - 1] 로 갈 수 있다면 true를 반환한다. 

 

 

이 때, 3번에서 [0][0]위치의 요소값도 범위 제한 내에 있는지 확인하는 코드를 잊지말자!

이부분에서 한참 틀렸다...