백준 - 15573 채굴

문제

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

15573번: 채굴

채굴기의 성능 D보다 강도가 약하고, 공기와 맞닿은 광물만 채굴할 수 있을 때 K 이상을 채굴할 수 있는 최소 강도 D를 구하는 문제였다.

문제 풀이

D가 최대 1000000이고, map의 크기가 최대 1000000인 문제였기 때문에 완전 탐색이 불가능했다. 이전에 이와 비슷한 문제를 푼 적이 있어서 바로 이분탐색으로 D를 구하는 방법을 생각했다. 각 D마다 bfs를 진행해 채굴 가능한 광물 수를 구한다면 시간복잡도는 O(N*log(N))이 나올 것이고 제한 시간인 2초 안에 충분히 해결 가능해 보였다. (N이 1000000)

 

먼저 입력받을 때 공기와 맞닿아 있는 광물, 즉 바닥면을 제외한 테두리를 저장해줬다. 이때 중복된 테두리가 2개 더 들어가지만 성능에 큰 영향을 미치지 않는다고 판단했다. 그리고 해당 map에서 강도가 가장 높은 광물의 s를 r로 정했다.

 

l은 0, r은 가장 큰 s로 이분탐색을 진행했고, 각 mid, 즉 각각의 D마다 bfs를 진행해 채굴 가능한 광물의 수를 구했다. 만약 채굴 가능한 광물의 수가 K 이상이라면 해당 강도는 가능한 것이기 때문에 answer를 갱신해주고 r을 mid-1로 옮겼다. 미만일 경우에는 불가능한 강도기 때문에 l을 mid+1로 옮겼다.

 

이분탐색이 모두 끝났을 때의 answer가 답이 된다.

/*
D를 이분탐색해 각 D마다 bfs로 채굴할 수 있는 광물 수 구하기
	공기와 맞닿은 모든 곳에서 bfs -> visit 안된 테두리에서만 bfs 하면 됨
	테두리 리스트 저장 (테두리는 항상 같음)
*/

typedef struct stone {
	int x;
	int y;
	int s; //강도
}stone;

int N, M, K;
vector<vector<int>> arr;
vector<vector<bool>> visit;
vector<pair<int, int>> border;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };


int cnt;

bool isInside(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	return false;
}

void bfs(int x, int y, int d) {
	queue<stone> q;

	q.push({ x,y,arr[x][y] });

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int s = q.front().s;
		q.pop();

		//채굴 불가능
		if (s > d) continue;
		cnt++;
		//상하좌우 광물 채굴 가능해짐
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (isInside(nx, ny) && !visit[nx][ny]) {
				visit[nx][ny] = true;
				q.push({ nx,ny,arr[nx][ny] });
			}
		}
	}
}

int main() {

	int l = 0;
	int r = 0;

	scanf("%d %d %d", &N, &M, &K);

	arr = vector<vector<int>>(N, vector<int>(M));
	visit = vector<vector<bool>>(N, vector<bool>(M,false));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &arr[i][j]);
			//테두리 저장
			if (i == 0 || j==0 || j==M-1) {
				border.push_back({ i,j });
			}
			r = max(r, arr[i][j]);
		}
	}

	//이분탐색 시작

	int answer = 1000000;

	while (l <= r) {
		int mid = (l + r) / 2;
		//printf("l: %d r: %d mid: %d\n", l, r, mid);
		//bfs로 캘 수 있는 광물 개수 구하기
		cnt = 0;
		visit = vector<vector<bool>>(N, vector<bool>(M, false));
		for (int i = 0; i < border.size(); i++) {
			int x = border[i].first;
			int y = border[i].second;
			if (!visit[x][y]) {
				visit[x][y] = true;
				bfs(x, y, mid);
			}
		}
		//printf("cnt: %d\n=================\n", cnt);
		if (cnt >= K) { //해당 강도 가능, 줄이기
			answer = min(answer, mid);
			r = mid - 1;
		}
		else l = mid + 1; //해당 강도 불가능, 늘리기
	}
	printf("%d", answer);

	return 0;
}

/*

*/