[BaekJoon] 백준 14502번 : 연구소

14502번 : 연구소

내가 생각한 풀이방법은 다음과 같다.

벽을 세우고 → 바이러스를 퍼트리고 → 안전구역 개수를 저장

벽을 세우는 과정은 0의 인덱스를 구해 세 개의 벽을 세울 수 있는 모든 경우를 구한다.

조합을 이용해 구했는데 최대 배열의 크기가 8X8 이라 괜찮을 것이라고 생각했다.

다음으로 벽을 세운 뒤 DFS 를 통해 바이러스를 퍼트린다.

바이러스가 다 퍼졌으면 Counter 를 통해 안전구역 개수를 저장한다.

최대값을 계속 갱신하면서 저장하면 마지막에 남는 값은 안전구역의 최대값이 된다.

---

import sys
from copy import deepcopy
from itertools import combinations
import collections


def countSafeArea(area, virus):
	queue = collections.deque(virus)
	visit = [[-1, 0], [0, 1], [1, 0], [0, -1]]

	while queue:
		curLoc = queue.popleft()

		for val in visit:
			visitRow = curLoc[0] + val[0]
			visitCol = curLoc[1] + val[1]

			if 0 <= visitRow < n and 0 <= visitCol < m:
				if area[visitRow][visitCol] == 0:
					area[visitRow][visitCol] = 2
					queue.append([visitRow, visitCol])

	return collections.Counter(sum(area, []))[0]


n, m = map(int, input().split())
data = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(n)]
zeroIndex, virusIndex = [], []
safeArea = 0

for i in range(n):
	for j in range(m):
		if data[i][j] == 0:
			zeroIndex.append([i, j])
		if data[i][j] == 2:
			virusIndex.append([i, j])

wallIndex = combinations(zeroIndex, 3)

for val in wallIndex:
	copyData = deepcopy(data)
	wall1, wall2, wall3 = val

	copyData[wall1[0]][wall1[1]] = 1
	copyData[wall2[0]][wall2[1]] = 1
	copyData[wall3[0]][wall3[1]] = 1

	safeArea = max(safeArea, countSafeArea(copyData, virusIndex))

print(safeArea)