BOJ 2842 집배원 한상덕

사용한 알고리즘

이분탐색, DFS

알고리즘 기초

파라메트릭 서치란 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟 값, 최대 값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것이다. (참조)

예제 그래프

1. 최소 높이와 최대 높이는 N*N 의 높이들 중에 한 값으로 정해진다. [ 3, 3, 4, 9, 5, 9, 8, 3, 7 ] - > [ 3, 4, 5, 7, 8, 9 ]
1. 위 예제에서 높이 범위가 [3, 8] 일때 성립하면, [2, 8], [3, 9]의 범위에 경우에도 모든 집을 갈 수 있다. 즉, [3, 8]에 대해서 성립되면, 최소 값이 3으로 고정되었다고 할때, 높이가 8 이상인 경우는 고려하지 않아도 된다.

알고리즘 순서

우체국의 시작점을 저장하고, 집의 개수를 센다.
N*N에 저장된 높이들을 저장하고, 이를 sorting 한다.
이 높이들이 저장된 배열이름을 ‘H’ 라고 하자.
먼저 H[0]가 최소값이라고 할때, H[1]~H[N*N] 사이에 모든 집에 배달 가능한 높이가 존재할 것이다.
이를 이분 탐색을 이용하여 높이를 찾아간다.
left = 1, right = N*N-1 라고 할때, mid = (left + right)/2
[ H[0], H[mid] ]가 배달부가 갈 수 있는 높이일때, 모든 집에 배달 가능한지를 판단한다.(BFS)
배달 가능하면, right = mid-1로 정한다.
배달 가능하지 않으면 left = mid+1로 정한다.

알고리즘 예시

시간 복잡도 계산

풀이

// baekjoon 2842 yechan
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;
const int MAX_N=51;
const int dx[8] = {-1,  0,  1, -1, 0, 1, -1, 1};
const int dy[8] = {-1, -1, -1,  1, 1, 1,  0, 0};

int N, totalNode, nodeCnt, height[MAX_N][MAX_N], sx, sy, ret=1e6;
int num[MAX_N*MAX_N];
vector<int> src;

char board[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

void dfs(int x, int y, int bottom, int top) {
	for (int d=0; d<8; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		if (visited[nx][ny]) continue;
		if (height[nx][ny] < bottom) continue;
		if (height[nx][ny] > top) continue;
		if (board[nx][ny] == 'K') nodeCnt--;
		visited[nx][ny]=true;
		dfs(nx, ny, bottom, top);
	}
}

bool indfs(int bottom, int top) {
	if (height[sx][sy] < bottom || top < height[sx][sy]) return false;
	memset(visited, 0, sizeof(visited));
	nodeCnt=totalNode;
	visited[sx][sy]=true;
	dfs(sx, sy, bottom, top);
	return nodeCnt==0;
}

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++) {
		scanf(" %s", board[i]);
		for (int j=0; j<N; j++) {
			if (board[i][j] == 'P') sx = i, sy = j;
			if (board[i][j] == 'K') totalNode++;
		}
	}

	int k=0;
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			scanf(" %d", &height[i][j]);
			num[k++]=height[i][j];
		}
	}

	sort(num, num+N*N);
	int pv=0;
	for (int i=0; i<N*N; i++) {
		if (pv != num[i]) src.push_back(num[i]);
		pv = num[i];
	}

	int sSize=src.size();
	for (int i=0; i<sSize; i++) {
		int left=i, right=sSize-1;
		while (left <= right) {
			int mid = (right + left)/2;
			if (indfs(src[i], src[mid])) right=mid-1, ret=min(ret, src[mid] - src[i]);
			else left=mid+1;
		}
	}
	printf("%d\n", ret);
	return 0;
}