boj.kr/14502 연구소 (gold4) 파이썬 풀이

1. 벽을 세울 수 있는 3개 좌표 추출하는 모든 경우에 대해 아래 2, 3 반복
2. bfs 방식으로 벽을 세운 후 전염결과 구하기
3. 전염후 안전지대 총 개수 계산

4. 안전지대 총 개수의 최대값을 출력

 

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

space = []
infected = []
for y in range(N):
    for x in range(M):
        if board[y][x] == 0:
            space.append((y, x))
        if board[y][x] == 2:
            infected.append((y, x))

dy = (0, 0, -1, 1)
dx = (-1, 1, 0, 0)
from collections import deque
def bfs(y, x, temp):
    dq = deque()
    dq.append((y, x))
    while dq:
        (cy, cx) = dq.popleft()
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<M and (temp[ny][nx] == 0 or temp[ny][nx] == 2) and visited[ny][nx] == 0:
                visited[ny][nx] += 1
                temp[ny][nx] = 2
                dq.append((ny, nx))

import copy
from itertools import combinations
safe_list = []
for combi in combinations(space, 3):
    visited = [[0] * M for _ in range(N)]
    temp = copy.deepcopy(board)
    for (y1, x1) in combi:
        temp[y1][x1] = 1
    for (y2, x2) in infected:
        visited[y2][x2] += 1
        bfs(y2, x2, temp)
    safe = 0
    for row in temp:
        safe += row.count(0)
    safe_list.append(safe)
print(max(safe_list))

 

브루트포스, BFS 를 사용하는 문제이다.