[백준_14502] 연구소 python

오늘 배운 점은,

조합을 구하는 재귀를 돌릴 때,

보다 빠른 방법을 찾았다는 것이다.

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n, m 입력
n, m = map(int, input().split())

# lab
lab = [
    list(map(int, input().split()))
    for _ in range(n)
]

# visited
visited = [
    [0] * m
    for _ in range(n)
]

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# check(x, y)
def check(x, y):
    # 범위 내에 있고, 방문한 적 없고, 벽이 아니면 이동 가능
    return in_range(x, y) and not visited[x][y] and lab[x][y] != 1

# bfs()
def bfs():
    while q:
        # 언팩킹
        x, y = q.popleft()

        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            # 다음 조사 위치
            nx, ny = x + dx, y + dy
            # 다음 위치로 갈 수 있으면
            if check(nx, ny):
                # 방문 표시 해주고
                visited[nx][ny] = 1
                # 큐에 넣어줌
                q.append((nx, ny))

# 큐 사용 준비
from collections import deque

# 큐
q = deque()

# calc()
def calc():

    global visited, ans

    # visited 초기화
    visited = [
        [0] * m
        for _ in range(n)
    ]

    # 벽 세워주기 -> 다시 없애줘야 함
    for wall in selected_pos:
        
        # 언팩킹
        x, y = wall

        # 벽 세워주기
        lab[x][y] = 1

    # 연구실 돌면서
    for i in range(n):
        for j in range(m):
            # 바이러스를 만나면
            if lab[i][j] == 2:
                # 방문표시해주고
                visited[i][j] = 1
                # 큐에 넣어주고
                q.append((i, j))
                # bfs() 호출
                bfs()
    
    # 바이러스가 퍼진 칸의 갯수
    virus = 0

    # 바이러스가 퍼진 칸 계산
    for i in range(n):
        for j in range(m):
            
            # 방문한 칸을 만나면
            if visited[i][j]:
                # 바이러스 칸의 수 추가
                virus += 1
    
    # 벽의 수 
    wall = 0

    # 벽의 수 계산
    for i in range(n):
        for j in range(m):

            # 벽을 만나면
            if lab[i][j] == 1:
                # 벽의 수 추가
                wall += 1
    
    # 총 안전 영역의 크기
    safe_zone = n * m - virus - wall

    # 안전 영역의 크기가 이전 계산보다 크다면
    if ans < safe_zone:
        # 바꿔줌
        ans = safe_zone
    
    # 벽 다시 빼주기
    for wall in selected_pos:
        
        # 언팩킹
        x, y = wall

        lab[x][y] = 0

# 설계
# empty_pos -> 비어있는 공간의 좌표를 기록해줄 리스트
empty_pos = []

# 연구실을 돌면서
for i in range(n):
    for j in range(m):
        # 빈 공간을 찾으면
        if not lab[i][j]:
            # 좌표를 기록
            empty_pos.append((i,j))
            
# 선택할 3개의 공간을 넣어 줄 리스트
selected_pos = []

# ans
ans = -1

# 서로다른 3칸의 조합을 만들어 주는 함수 
def make_comb(curr_idx, cnt):
    
    # 종료조건
    if cnt == 3:
        # 계산
        calc()
        return
    
    if curr_idx == len(empty_pos):
        return

    # 조합 만들기
    selected_pos.append(empty_pos[curr_idx])
    make_comb(curr_idx + 1, cnt + 1)
    selected_pos.pop()

    make_comb(curr_idx + 1, cnt)

# 함수 호출
make_comb(0, 0)

# 출력
print(ans)