[백준 5846] Tractor

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

5846번: Tractor

#include <cstdio>
#include <queue>
#include <algorithm>
int N;
int field[500 + 2][500 + 2];
int visited[500 + 2][500 + 2];
int max_val;
int min_val = 0x7fffffff;
int half;

struct _st
{
	int x;
	int y;
};

std::queue<_st> Q;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &field[i][j]);
			max_val = (field[i][j] > max_val) ? field[i][j] : max_val;
			min_val = (field[i][j] < min_val) ? field[i][j] : min_val;
		}
	}
	half = ((N * N) + 1) / 2;		// 들판의 총 격자수가 홀수이면 반올림 개수만큼 방문해야 한다.  
}


int BFS(int D, int x, int y)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};			// BFS 여러번 호출되므로 큐 초기화
	Q.push({ x, y });
	visited[x][y] = 1;
	int cnt = 1;	// 방문할 수 있는 영역의 수	// 처음 좌표 방문 했으므로 1로 초기화 !!!!!

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;		// 영역을 벗어났다면 스루
			if (visited[nx][ny]) continue;	 // 방문했다면 스루
			if (abs(field[nx][ny] - field[data.x][data.y]) > D) continue;	// 해당 성능의 트랙터로 못감 
			visited[nx][ny] = 1;
			Q.push({ nx, ny });
			cnt++;
		}
	}
	return cnt;
}



bool chk(int D)
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) continue;
			int area = BFS(D, i, j);
			if (area >= half) {
				return true;
			}
		}
	}
	return false;	// 영역을 모두 탐색할 때 까지도 true를 리턴하지 못했다면,
					// 해당 성능의 트랙터로는 일 못함 
}



int get_min()
{
	int s = 0;	// 높이 차이가 안날 수 도 있다. 
	int e = max_val - min_val;
	int D = 0;

	while (s <= e) {
		int m = (s + e) / 2;
		if (chk(m)) {
			D = m;
			e = m - 1;	// 최소의 값 찾기 위해
		}
		else s = m + 1;
	}
	return D;
}


int main()
{
	input();
	int ans = get_min();
	printf("%d\n", ans);
	return 0;
}

단순 BFS는 아니고,, 최소 성능 D에 대한 parametric search가 필요한 문제이다. 

 

 

// input( ) 함수

D를 찾는 과정에서 가장 큰 값 e를 1,000,000로 설정해도 되지만, 예컨대 예제 1번과 같은 경우 가장 큰 값이 9이므로 백만까지 볼 필요가 없다. 따라서 입력받는 데이터 중 가장 큰 값과 가장 작은 값을 미리 찾아놓고, 두 값의 차를 e로 설정해줄 것이다. 

한편 농부 존이 들판의 어느 곳에서 출발하더라도, 들판의 절반 이상을 돌아다녀야 하고, 총 격자 수가 홀수이면 반올림 개수만큼 방문할 수 있으므로 해당 변수 half 를 (N * N + 1) / 2로 설정한다. 

 

 

// get_min( ) 함수

성능 D에 대한 파라매트릭 서치를 진행하는 부분이다. 

이때 들판의 모든 높이가 같아서 D == 0으로 들판의 절반 이상을 탐색할 수 있는 경우가 존재할 수 있으므로 가장 작은 값 s 는 반드시 0으로 설정해준다(min_val 이 아님).

구조는 이분탐색과 동일한데, D의 후보값 들 중에서 가장 "작은 것을 결정"해야 한다. 

따라서 m값이 정해졌을 때, chk 함수를 통해 해당 성능으로 들판의 절반 이상을 탐색할 수 있으면 m을 후보에 등록한다. 그러고 "최소"의 성능을 찾기 위해 가장 큰 값 e 를 m - 1로 갱신한다. 

chk 함수가 false를 리턴한다면 더 높은 성능이 필요하다. 따라서 가장 작은 값 s를 m + 1로 갱신한다. 

 

 

// chk( ) 함수

맵을 스캐닝하며 방문하지 않은 좌표에 대하여 BFS 함수를 돌린다. 

만약 해당 점으로부터 이동할 수 있는 칸의 개수가 들판의 절반 이상이라면 true를 리턴한다. 

맵을 전체 탐색했는데도 해당 함수를 빠져나가지 못한 경우, 넘겨받은 파라미터 D로는 들판의 절반 이상을 탐색하지 못하는 것이다. 따라서 false를 리턴한다. 

 

 

// BFS( ) 함수

주의!!! 해야할 점은 넘겨받은 파라미터 (x, y) 좌표에서 시작하고 해당 칸은 방문했으므로 visited[x][y] = 1이고 cnt의 초기값은 1이다 (!!!!!) 이거 안해줘서 3번 틀렸다.. 흑_흑.. 

나머지는 일반적인 BFS와 동일하게 진행되고, 다만 이동하려는 좌표와 현재 좌표의 높이 차가 D 보다 크다면 이동할 수 없다. 

 

 

잔실수좀 작작하자..