백준 1981 c++ "배열에서 이동" -PlusUltraCode-

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

 

[필자 사고]

평범한 BFS탐색문제이지만 이분탐색이 들어가 색다른 느낌이 든다.

미드값을 가지고 BFS 0부터 mid값부터 시작하여 i부터 mid값+ i 의 숫자들은 모두 false 형태로 바꾸고

탐색을 진행하다 성공하면 end값을 더 줄이고 그렇지 않으면 start값을 늘리는 형식..

이분탐색을 더욱 깊이 있게 배워나가는 시간이였다.

[코드 해설]

 

• 입력 처리 (Input 함수)
  • 사용자로부터 NxN 크기의 2차원 배열(arr)과 그 값들을 입력받는다.
  • 배열의 각 값을 읽으면서 최대값(maxValue)과 최소값(minValue)을 갱신한다.
• BFS를 활용한 경로 검증 (BFS 함수)
  • 특정 diff 값을 기준으로 이동 가능한 경로가 존재하는지 확인한다.
  • minValue부터 maxValue까지의 값을 기준으로, 현재 기준값 i와 i + diff 사이의 값만 이동 가능하도록 설정한다.
  • BFS는 (0,0)부터 시작하여, visited 배열을 사용해 이미 방문했거나 이동 불가능한 칸을 처리한다.
  • BFS가 (N-1, N-1)까지 도달하면 true를 반환하고, 그렇지 못하면 false를 반환한다.
• 게임 로직 (Game_Start 함수)
  • 이진 탐색을 이용하여 최소의 diff 값을 찾는다.
  • start는 0, end는 (maxValue - minValue)로 초기화하고, mid 값을 중심으로 BFS(mid)를 호출한다.
  • BFS가 true를 반환하면 더 작은 diff 값을 탐색하기 위해 end를 줄이고, false를 반환하면 start를 증가시킨다.
  • 탐색이 끝나면 최소 diff 값을 출력한다.
• 메인 함수
  • Input 함수로 데이터를 초기화한 뒤, Game_Start 함수를 호출하여 결과를 출력한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N;
vector<vector<int>> arr;
int maxValue = -1;
int minValue = 987;
bool visited[100][100];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };

void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(N);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
			if (maxValue < arr[i][k]) {
				maxValue = arr[i][k];
			}
			if (minValue > arr[i][k]) {
				minValue = arr[i][k];
			}
		}
	}
}

bool BFS(int diff) {
	queue < pair<int, int>> myQueue;

	for (int i = minValue; i <= maxValue; i++) {
		memset(visited, true, sizeof(visited));

		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (i <= arr[j][k] && arr[j][k] <= i + diff) visited[j][k] = false;
			}
		}

		myQueue.push({ 0,0 });

		while (myQueue.empty() == 0) {
			int sero = myQueue.front().first;
			int  garo = myQueue.front().second;
			myQueue.pop();

			if (visited[sero][garo] == true)continue;
			visited[sero][garo] = true;

			if (sero == N - 1 && garo == N - 1)return true;

			for (int i = 0; i < 4; i++) {
				int nextSero = sero + dy[i];
				int nextGaro = garo + dx[i];

				if (nextSero >= 0 && nextSero < N && nextGaro >= 0 && nextGaro < N) {
					myQueue.push({ nextSero,nextGaro });
				}
			}
		}

	}

	return false;
}

void Game_Start() {
	int start = 0;
	int end = maxValue - minValue;
	int mid;

	while (start <= end) {
		mid = (start + end) / 2;
		if (BFS(mid) == true) end = mid - 1;
		else start = mid + 1;
	}
	

	cout << start << '\n';

}

int main(void) {
	Input();
	Game_Start();
}