마쏘's 개발 성장기

해당 문제의 백준 사이트 링크
https://www.acmicpc.net/problem/14502

입력)

- 세로 크기 N과 가로 크기 M (3 <= N, M <= 8)

- 연구소 모양을 나타내는 N*M 크기의 2차원 정수 배열(0 or 1 or 2)

- 2<= 바이러스(2)의 개수 <= 10

출력)

-  얻을 수 있는 안전 영역의 최대 크기

입, 출력 분석)

- (3 <= N, M <= 8) 이므로 안전 영역의 최대 크기가 정수를 넘지 않는다. 따라서 integer로 정의한다.

핵심)

- 주어진 연구소 지도에 벽 3개를 세운다.

- 바이러스를 퍼트린다.

- 바이러스가 다 퍼졌으면 안전 영역을 구한다.

위 과정을 주어진 연구소 지도에 벽 3개를 세우는 모든 경우로 다 해본다.

예시 분석)

- (생략)

실수) 

- 예전에 풀었던 것을 다시 보면서 올리는 중이라 어떤 부분에서 실수를 했는지 기억이 잘 안나지만,

 첫 삼성 기출 문제였던 만큼 문제를 이해하고, 문제 유형이나 구현 및 설계까지 시간이 오래 걸렸던 것으로 기억한다.

- 이런 걸 가끔 볼 때마다 나도 조금씩 실력이 늘고 있다는 생각이 든다!

구현)

#include <stdio.h>
#include <queue>
using namespace std;

int N = 0, M = 0, maxArea = 0;
int lab[9][9] = { 0, };
int virus[9][9] = { 0, };
queue<pair<int, int>> vPos;

int dx[4] = { 0, -1, 0, 1 }; // 왼, 위, 오, 아래
int dy[4] = { -1, 0, 1, 0 };

void spreadVirus() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			virus[i][j] = lab[i][j];
			if (lab[i][j] == 2)
				vPos.push({ i,j });
		}
	}
	while (!vPos.empty()) {
		int vx = vPos.front().first;
		int vy = vPos.front().second;
		vPos.pop();
		int x = 0, y = 0;
		for (int i = 0; i < 4; i++) {
			x = vx + dx[i];
			y = vy + dy[i];
			if (x < 0 || y < 0 || x >= N || y >= M)
				continue;
			if (virus[x][y] == 0) {
				virus[x][y] = 2;
				vPos.push({ x, y });
			}
		}
	}
}

void buildWall(int idx, int cnt) {
	if (cnt == 3) {
		spreadVirus(); // 벽 3개를 다 세웠으면 바이러스 퍼트리기
		int area = 0;
		for (int i = 0; i < N; i++) { // 안전 영역 계산하기
			for (int j = 0; j < M; j++) {
				if (virus[i][j] == 0)
					area += 1;
			}
		}
		area > maxArea ? maxArea = area : maxArea;
		return;
	}
	int nx = 0, ny = 0;
	for (int i = idx; i < (N*M); i++) {
		nx = i / M; ny = i%M;
		if (lab[nx][ny] == 0) {
			lab[nx][ny] = 1;
			buildWall(nx*M + ny, cnt + 1);
			lab[nx][ny] = 0;
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%d", &lab[i][j]);
	}
	buildWall(0, 0); // 벽 3개 세우기
	printf("%d", maxArea);
	return 0;
}