백준 14502 연구소

설계:

• '감염 영역'
  • BFS를 통해 얻는 건 '안전 영역'의 여집합의 크기이기 때문에 해당 집합을 칭하는 '감염 영역'이라는 개념 도입
  • BFS를 수행할 때 벽(1)의 개수는 고정이기 때문에 '안전 영역'(0)의 최대화는 '감염 영역'(2)의 최소화임
  • trimming
    • BF에서 현재까지 최소 감염영역의 크기(ma)를 BFS의 인자로 넘겨주고, BFS 중 감염영역이 ma 이상이 되면 어짜피 ma 갱신이 불가함으로(정답에 영향 주지 않음) 탐색 중지
• 0의 좌표를 배열화
  • BF body의 for문으로 2차원인 map을 커버하려면 1. '1일 경우 skip', 2. r과 c 모두 인자로 유지하면서 'c가 C - 1이 되면 ++r, c = 0'의 예외처리를 해줘야 한다.
  • BF는 시간 복잡도((R X C)!)가 높기 때문에 body의 예외처리를 최소화해야 한다.
  • 높은 시간복잡도를 대체하기 위해 input을 읽어들일 때 R X C만큼의 시간복잡도로 0의 좌표를 1차원 배열에 저장

주의:

• 탐색에서 첫 위치도 위치별 처리의 대상이 되어야 한다.

수정:

<탐색 관련>

• 탐색 중지 조건 누락
  • 바이러스가 wall에 닿으면 더 이상 확산하지 못 한다.
• BF에서 map의 변형
  • BF에서 map 복사를 방지하기 위해 자식 call 전후로 map 수정, 복구를 배치한다.
  • map 수정, 복구 사이에 예외처리 결과로 continue, break, return등이 발생하면 뒤에 위치한 map 복구를 bypass한다.
  • 이를 방지하기 위해 jump 전 map 복구를 삽입한다.
• 재귀구조
  • l == 3일 때 BFS를 한 번 수행하고 바로 return한다고 생각했지만 이는 아래 그림의 왼쪽과 같이 잘못된 재귀구조(BF l==3이 leaf라고 생각)
  • l == 3일 때도 for문에 해당하는 모든 case들에 대해 BFS를 수행해야 한다.(BFS가 leaf임)

<기타>

• callee의 함수 선언은 caller 함수 선언 위로 올리기

• visited를 공유하는 탐색
  • visited되지 않을 경우만 탐색한다는 조건을 삽입해야 한다.
• getchar() 문자로 받기
  • 이에 대한 switch 분기문의 case 조건도 문자여야 한다.

소요시간:

 

개선:

• BF 예외처리
  • l == 3일 때 자식 호출 전에 예외처리, l == 4일 때 for문 전에 예외처리
    • 둘다 연산 횟수는 동일하나 후자가 더 자연스럽고 관습에 부합한다.

 

#include <stdio.h>
#include <utility>
#include <queue>

using namespace std;

int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };

#define IN(n, m) (0 <= (n) && (n) < N && 0 <= (m) && (m) < M)

/* 자식 함수 선언을 부모 선언 위에 올리기 */
void BFS(bool w[][8], bool vs[][8], int N, int M, int vn, int vm, int &a, int ma) {
	pair<int, int> rt = make_pair(vn, vm);

	vs[vn][vm] = 1; ++a;
	queue<pair<int, int>> q;
	q.push(rt);

	while (!q.empty()) {
		auto pt = q.front();
		q.pop();

		for (int d = 0; d < 4; ++d) {
			int cn = pt.first + dn[d], cm = pt.second + dm[d];

			if (!IN(cn, cm) || w[cn][cm] || vs[cn][cm])	/* wall 조건 누락 */
				continue;

			vs[cn][cm] = 1;	++a;
			if (a >= ma)
				return;
            
			pair<int, int> cd = make_pair(cn, cm);
			q.push(cd);
		}
	}
}

/* 첫 좌표도 처리하기 */
/* 인자 너무 많음 */
/* 예외처리 return 후에도(l == 3) 자료구조 변환 되돌려놔야 (w[e[ei].first][e[ei].second] = 0;)*/
/* 예외처리를 l == 3에서 하는 것과 l == 4에서 하는 것의 연산 횟수 차이는 없지만 l == 4가 더 자연스럽과 관습과 더 부합하는 듯 */
int BF(pair<int, int> e[], int en, int ei, int l, bool w[][8], int N, int M, pair<int, int> v[], int vn, int ma) {
	if (l == 4) {
		int a = 0; bool vs[8][8] = { 0 };
		for (int vi = 0; vi < vn; ++vi)
			if (!vs[v[vi].first][v[vi].second])		/* 방문하지 않았을 때만 BFS 돌려야 */
				BFS(w, vs, N, M, v[vi].first, v[vi].second, a, ma);	/* 자식은 BFS만 하고 return x en - 2개의 세번째 선택 후에 BFS 그 모든 결과의 min만 반환 */
		return a;
	}

	for (; ei < en; ++ei) {
		w[e[ei].first][e[ei].second] = 1;

		int a = BF(e, en, ei + 1, l + 1, w, N, M, v, vn, ma);

		if (a < ma)
			ma = a;

		w[e[ei].first][e[ei].second] = 0;
	}
	return ma;
}

int main() {
	int N, M;
	scanf("%d%d", &N, &M);

	bool w[8][8] = { 0 };
	pair<int, int> e[64], v[10];
	int en = 0, vn = 0;
	for (int n = 0; n < N; ++n)
		for (int m = 0; m < M; ++m) {
            int o;
            scanf("%d", &o);
			switch (o) {	/* char로 받았으니 case도 문자여야 */    /* 이 문제 입력에는 int로 받는 것이 더 어울림 */
			case 0: e[en++] = make_pair(n, m); break;
			case 1: w[n][m] = 1; break;
			case 2: v[vn++] = make_pair(n, m); break;
			}
		}
    
	printf("%d", en - 3 - BF(e, en, 0, 1, w, N, M, v, vn, 64) + vn);    /* vn 더해야 답이 나옴 */

	return 0;
}