알고리즘 :: 백준 :: 14502 - 연구소

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)
• 0은 빈 칸, 1은 벽, 2는 바이러스
  
  • 2 ≤ 바이러스 개수 ≤ 10
  • 3 ≤ 빈 칸
• 출력: 안전영역의 최대크기

✏️ 문제풀이

안전영역의 최대 크기를 구하기 위해서는 주어진 빈칸들 중 3칸을 선택할 수 있는 모든 경우의 수를 따져봐야 합니다.

• 연구실 크기는 최대 8 × 8 = 64칸입니다.
• 최악의 경우, 벽이 하나도 없고 바이러스가 2개 있다면, 3개의 벽을 세울 수 있는 경우는 62 × 61 × 60 = 약 22만
• 충분히 모든 경우의 수를 계산할 수 있습니다.

 

로직은 다음과 같습니다.

1. 선택한 빈칸 3칸을 `1`로 만들어 벽을 세웁니다.
2. DFS 또는 BFS를 이용해서 시뮬레이션을 돌립니다. 각 바이러스마다 갈 수 있는 모든 빈칸마다 방문표시하며 퍼집니다.
3. 안전영역의 넓이를 계산합니다.최댓값이라면 정답을 갱신합니다.
4. 1번에서 세웠던 벽을 다시 `0`으로 만들어 빈칸으로 롤백합니다.
5. 다음 빈칸 조합을 찾아 나섭니다. 1번으로 돌아갑니다

 

시뮬레이션을 할 때 주의해야 할 점이 있다면 연구실의 복사본에서 시뮬레이션을 해야한다는 점입니다. 바이러스가 퍼지며 연구실 값에 영향을 주기 때문에 사본을 만들어 시뮬레이션을 돌려야 합니다. 단, 벽을 세우고 벽을 허무는 것은 원본에서 합니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

constexpr int dy[] = {-1, 0, 1, 0};
constexpr int dx[] = {0, 1, 0, -1};
enum type { EMPTY, WALL, VIRUS };

int N, M;
array<array<int, 8>, 8> lab, cpLab;
vector<pair<int, int>> virus;

inline int getCount(const auto& lab) {
	int ret = 0;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			if (lab[y][x] == type::EMPTY) ret++;
	return ret;
}

void solve(int y, int x) {
	cpLab[y][x] = type::VIRUS;
	for (int i = 0; i < 4; ++i){
		int ny = y + dy[i], nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
		if (cpLab[ny][nx] != type::EMPTY) continue;
		solve(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N >> M;
	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < M; ++x) {
			cin >> lab[y][x];
			if (lab[y][x] == type::VIRUS) virus.push_back({y, x});
		}
	}
	
	int ans = 0;
	
	for (int i = 0, lim = N * M; i < lim; ++i) {
		int ay = i / M, ax = i % M;
		if (lab[ay][ax] != type::EMPTY) continue;
		lab[ay][ax] = type::WALL;
		
		for (int j = i + 1; j < lim; ++j) {
			int by = j / M, bx = j % M;
			if (lab[by][bx] != type::EMPTY) continue;
			lab[by][bx] = type::WALL;
			
			for (int k = j + 1; k < lim; ++k) {
				int cy = k / M, cx = k % M;
				if (lab[cy][cx] != type::EMPTY) continue;
				lab[cy][cx] = type::WALL;
				cpLab = lab;
				for (const auto& i : virus) solve(i.first, i.second);
				ans = max(ans, getCount(cpLab));
				lab[cy][cx] = type::EMPTY;
			}
			lab[by][bx] = type::EMPTY;
		}
		lab[ay][ax] = type::EMPTY;
	}
	cout << ans;
}

 

🔗 코드 링크

 

• `solve()` 함수에서 DFS를 이용해서 시뮬레이션을 돌리고 있습니다.

🕧 결과