[G3] 백준 15573번 채굴 C++ 너비 우선 탐색, 매개 변수 탐색

리뷰

 

시간이 생각보다 느려서 최적해인 방법은 아닌듯 하다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• M : 맵 정보를 저장할 2차원 배열
• v : 방문 정보를 저장할 2차원 배열
• n, m : 맵의 세로/가로 크기를 저장할 변수
• k : 채굴할 광물의 최소 개수를 저장할 변수
• Pos : 위지 정보를 정의할 구조체
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. init

int init(queue<Pos>& q, int d) {
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		v[i][0] = true;
		if (M[i][0] <= d) {
			++cnt;
			q.push({ i, 0 });
		}

		if (m == 1) continue;
		v[i][m - 1] = true;
		if (M[i][m - 1] <= d) {
			++cnt;
			q.push({ i, m - 1 });
		}
	}

	for (int j = 1; j < m - 1; ++j) {
		v[0][j] = true;
		if (M[0][j] <= d) {
			++cnt;
			q.push({ 0, j });
		}
	}
	return cnt;
}

 

초기 공기와 맞닿은 광물을 확인하고 채굴이 가능할 경우 큐에 삽입하기 위한 함수

 

2. bfs

bool bfs(int d) {
	memset(v, 0, sizeof(v));
	queue<Pos> q;
	int cnt = init(q, d);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		if (cnt >= k) return true;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = true;
				if (M[nx][ny] <= d) {
					++cnt;
					q.push({ nx, ny });
				}
			}
		}
	}

	return false;
}

 

d의 강도로 k개 이상의 광물을 채굴할 수 있는지 여부를 반환하기 위한 함수

 

 

문제풀이

1. n, m, k값을 입력 받고, 변수 mx를 0으로 초기화한다.
2. n*m크기의 맵을 초기화하고, 가장 큰 광물의 강도를 mx에 저장한다.
3. 변수 l을 1로, r을 mx로, d를 mx로 초기화한다.
4. l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.
5. 변수 mid를 l+r을 2로 나눈 몫으로 저장한다.
6. bfs함수에 mid를 매개변수로 전달하고, mid강도로 k개 이상의 광물을 채굴할 수 있는지를 확인한다.
7. bfs함수의 반환값이 true일 경우 d를 mid로 저장하고, r을 mid-1로 저장한다.
8. bfs함수의 반환값이 false일 경우 l을 mid+1로 저장한다.
9. while루프가 종료된 후 d에 저장된 값을 출력한다.

 

트러블 슈팅

1. 이분 탐색을 수행할때 while루프의 조건을 l<r로 설정하여 WA를 받았다.
2. while루프의 조건을 l<=r로 수정하여 AC를 받았다.

 

참고 사항

1. 공기와 맞닿는 광물을 미리 큐에 넣어두고 매번 복사해서 사용하려 했으나 구현이 복잡해 질 것 같아 포기했다.
2. 조기 종료를 처리하기 위해 구조체 복사 대신 pair<int, int>사용, memset대신 int기반의 방문 처리, init함수에서 cnt가 k이상이 되었을 경우 조기 종료 등 가지치기를 이것저것 추가해보았으나 오히려 시간 복잡도가 더 늘어났다.
3. 아무래도 광물의 강도가 최대 백만이라 위 가지치기보단 bfs함수를 효율적으로 수행하는 게 더 효과가 있는 듯 하다.

 

정답 코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int N = 1000;
int M[N][N];
bool v[N][N];
int n, m, k;
struct Pos {
	int x, y;
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

int init(queue<Pos>& q, int d) {
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		v[i][0] = true;
		if (M[i][0] <= d) {
			++cnt;
			q.push({ i, 0 });
		}

		if (m == 1) continue;
		v[i][m - 1] = true;
		if (M[i][m - 1] <= d) {
			++cnt;
			q.push({ i, m - 1 });
		}
	}

	for (int j = 1; j < m - 1; ++j) {
		v[0][j] = true;
		if (M[0][j] <= d) {
			++cnt;
			q.push({ 0, j });
		}
	}
	return cnt;
}

bool bfs(int d) {
	memset(v, 0, sizeof(v));
	queue<Pos> q;
	int cnt = init(q, d);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		if (cnt >= k) return true;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = true;
				if (M[nx][ny] <= d) {
					++cnt;
					q.push({ nx, ny });
				}
			}
		}
	}

	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	int mx = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> M[i][j];
			if (mx < M[i][j]) mx = M[i][j];
		}
	}

	int l = 1, r = mx, d = mx;
	while (l <= r) {
		int mid = (l + r) / 2;

		if (bfs(mid)) {
			d = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << d;
}