백준 1981 - 배열에서 이동(C++)

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

1981번: 배열에서 이동

BFS와 이분 탐색을 해야하는 문제였습니다.

문제 조건

출력 예시

N*N 배열에서 (1,1) -> (N,N) 까지 도착하는데 경로 값의 최댓값과 최솟값의 차이의 최솟값을 구하는 문제입니다.

저는 N*N 배열의 값을 모두 저장한 뒤, 중복값을 없앴습니다. 그 뒤에 (0~0) -> (0~1)등으로 값을 늘려가면서 해당 범위에 있는 경로만을 통해서 갈 수 있게 만들었습니다.

 

문제의 예시를 통해서 설명하겠습니다.

문제 접근 방법

1. N*N 배열의 값을 받은뒤, 백터에 저장한다.

2. 백터를 오름차순으로 정렬한 뒤, 중복된 값을 없앤다.

3. low = 0, high = 0으로 정한 뒤, 백터의 (low ~ high) 값을 통해서 이동할 수 있는지를 확인한다.

4. 이동할 수 있는지의 여부에 따라 low 또는 high를 증가한다.

5. 이동할 수 있는 경우에는 최솟값을 비교하여 저장한다.   

 

 

문제 접근 방법 - 2번

sort(number.begin(), number.end());
number.erase(unique(number.begin(), number.end()), number.end());

위의 erase를 사용한다면 중복된 값을 없앨 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
int miro[101][101];
int check[101][101];
vector<int> number;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct qu {
	int x;
	int y;
}qu;

int bfs(int low, int high) {
	queue<qu> q;
	if (number[low] <= miro[1][1] && number[high] >= miro[1][1]) {
		q.push({ 1,1 });
		check[1][1] = 1;
	}
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (x == N && y == N) break;
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= N) {
				if (check[xx][yy] == 0 && number[low] <= miro[xx][yy] && number[high] >= miro[xx][yy]) {
					check[xx][yy] = 1;
					q.push({ xx,yy });
				}
			}
		}
	}
	if (check[N][N] == 1) {
		return 1;
	}
	else {
		return 2;
	}
}

void solve() {
	sort(number.begin(), number.end());
	number.erase(unique(number.begin(), number.end()), number.end());
	int low = 0;
	int high = 0;
	int result = 9876;
	while (low < number.size()) {
		memset(check, 0, sizeof(check));
		int ans = bfs(low, high);
		if (ans == 1) {
			result = min(result, number[high] - number[low]);
			low++;
		}
		else {
			if (high < number.size() - 1) high++;
			else break;
		}
	}
	cout << result;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> miro[i][j];
			number.push_back(miro[i][j]);
		}
	}
	solve();
	return 0;
}