[백준 9879] Cross Country Skiing (C++)

문제 링크: www.acmicpc.net/problem/9879

9879번: Cross Country Skiing

1. 주의할 점

- 이분탐색을 사용하여 웨이포인트에서 시작하여 Mid만큼의 차이 이하가 나면서 다음칸으로 넘어갈 수 있는지 BFS 탐색한다

- 첫번째 웨이포인트에서 다른 웨이포인트까지 도달 가능하다면, 모든 웨이포인트는 서로 도달이 가능하다(첫번째 웨이포인트를 거쳐서 갈 수 있으므로)

 

2. 구현

- 각 지형의 높이에 대한 정보를 Arr[][]배열에 입력받으며, 이중에서 가장 큰값을 R에 저장한다

- 웨이포인트를 Waypoint 벡터에 모두 저장한다

- L=0, R= Arr[][]값중에서 최고에서 이분탐색을 시작하며, Mid값으로 BFS를 거친다. BFS가 끝난 이후, 모든 Waypoint를 방문했다면 True를, 아니라면 False를 반환하며 Mid값을 조정한다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
struct info {
	int x, y;
};
info tmp;
int arr[500][500];
bool check[500][500];
int row, col, val;
vector<info> waypoint;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool bfs(int mid) {
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			check[i][j] = false;
	queue<info> q;
	tmp.x = waypoint[0].x;
	tmp.y = waypoint[0].y;
	q.push(tmp);
	check[tmp.y][tmp.x] = true;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < col && ny < row && abs(arr[ny][nx] - arr[cy][cx]) <= mid && !check[ny][nx]) {
				check[ny][nx] = true;
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
			}
		}
	}
	for (int i = 1; i < waypoint.size(); i++) {
		int cx = waypoint[i].x;
		int cy = waypoint[i].y;
		if (!check[cy][cx])
			return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col;
	int l = 0, r = 0, mid, result;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			r = max(r, arr[i][j]);
		}
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> val;
			if (val == 1) {
				tmp.x = j;
				tmp.y = i;
				waypoint.push_back(tmp);
			}
		}
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (bfs(mid)) {
			result = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	cout << result;
	return 0;
}