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

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

1981번: 배열에서 이동

1. 주의할 점

- 두 포인터를 사용하여 풀어야 한다

- 검사를 할 때 마다 Check[][]배열을 False로 초기화 해야 한다

 

2. 구현

- 배열을 입력받고, 배열의 최소값과 최대값을 구한다

- L,R을 배열의 최소값으로 설정하고 While문을 시작한다(L~R 사이여야 이동 가능)

- 만약 시작지점이 L보다 작거나 R보다 크다면 R++를 한다

- 시작지점 L이상 +  R이하면 시작하고 Check[][] 배열을 초기화한다

- BFS를 수행하며 이동하려는 칸이 방문하지 않았고, L이상 R이하라면 이동한다

- 만약 오른쪽 아래까지 갔다면(목적지) Avail을 True 로 설정하고 BFS를 종료한다

- Avail==True인 경우, Result와 R-L를 비교하여 작은 값을 Result에 할당한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int x, y;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int num, mini = 201, maxi = -1, l, r, mid, result = 201;
int arr[100][100];
bool check[100][100];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			cin >> arr[i][j];
			mini = min(mini, arr[i][j]);
			maxi = max(maxi, arr[i][j]);
		}
	l = mini, r = mini;
	while (l <= r && r <= maxi) {
		if ((arr[0][0] < l) || arr[0][0] > r) {
			r++;
			continue;
		}
		bool avail = false;
		queue<info> q;
		for (int i = 0; i < num; i++)
			for (int j = 0; j < num; j++)
				check[i][j] = false;
		tmp.x = 0;
		tmp.y = 0;
		q.push(tmp);
		while (!q.empty()) {
			int cx = q.front().x;
			int cy = q.front().y;
			q.pop();
			if (cx == num - 1 && cy == num - 1) {
				avail = true;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < num && ny < num && !check[ny][nx]) {					
					if (l<=arr[ny][nx] && arr[ny][nx]<=r) {
						tmp.x = nx;
						tmp.y = ny;
						q.push(tmp);
						check[ny][nx] = true;
					}
				}
			}
		}
		if (avail) {
			result = min(result, r - l);
			if (l != r)	l++;
			else r++;
		}
		else
			r++;
	}
	cout << result;
	system("pause");
	return 0;
}