▶ 골드4 (BFS + 브루트포스)
풀이
n, m의 크기가 10 이하고 벽의 개수가 무조건 3개이기 때문에 브루트포스임을 알게 되었습니다.
처음에는 백트래킹을 이용해서 벽 3개를 세우고, BFS를 이용해서 바리어스 확산 칸의 개수를 세서 최댓값을 구하는 방법으로 구현했는데, 시간 초과가 발생하였습니다.
그래서 백트래킹 대신 파이썬의 combinations를 이용해서 완탐으로 벽 3개의 조합을 구하는 방식으로 수정하였습니다.
코드
# 14502_연구소
from collections import deque
from itertools import combinations
from copy import deepcopy
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
laboratory = [list(map(int, input().split())) for _ in range(n)]
x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]
empty = [] # 빈공간 위치
virus = [] # 바이러스 위치
answer = 0
for i in range(n):
for j in range(m):
if laboratory[i][j] == 0:
empty.append((i, j))
elif laboratory[i][j] == 2:
virus.append((i, j))
def BFS():
copy_lab = deepcopy(laboratory)
queue = deque(virus)
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + x_dir[i]
ny = y + y_dir[i]
if 0 <= nx < n and 0 <= ny < m:
if copy_lab[nx][ny] == 0:
queue.append((nx, ny))
copy_lab[nx][ny] = 2
global answer
answer = max(answer, sum(row.count(0) for row in copy_lab))
for a, b, c in combinations(empty, 3):
# print(a, b, c)
for x, y in [a, b, c]:
laboratory[x][y] = 1
BFS()
for x, y in [a, b, c]:
laboratory[x][y] = 0
print(answer)
'Algorithm > Baekjoon' 카테고리의 다른 글
15681_트리와 쿼리 (0) | 2025.03.12 |
---|---|
20922_겹치는 건 싫어 (0) | 2025.03.09 |
11123_양 한마리... 양 두마리... (0) | 2025.03.07 |
15558_점프 게임 (0) | 2025.02.26 |
16719_ZOAC (0) | 2025.02.25 |