[백준 파이썬] 14502번 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

from collections import deque
import copy
from sys import stdin

N, M = map(int, stdin.readline().split())
arr = [list(map(int, stdin.readline().split())) for _ in range(N)]


dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

result = 0

def bfs():
    global result
    deq = deque()
    temp = copy.deepcopy(arr)
    for i in range(N):
        for j in range(M):
            if temp[i][j] == 2:
                deq.append((i,j))
    while deq:
        r, c = deq.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < N and 0 <= nc < M and temp[nr][nc] == 0:
                temp[nr][nc] = 2
                deq.append((nr, nc))

    # 0 개수 세아리기
    tmp = 0
    for i in range(N):
        for j in range(M):
            if temp[i][j] == 0:
                tmp += 1
    result = max(result, tmp)


# 벽 3개 만들기
def wall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0:
                arr[i][j] = 1
                cnt += 1
                wall(cnt)
                cnt -=1
                arr[i][j] = 0
wall(0)
print(result)

 

<풀이방법>

bfs문제로 벽 3개 만드는 부분이 포인트였다. 벽 3개를 만들 수 있는 모든 경우의 수를 반복하여 최대값을 구해야한다.

 

<리뷰>

아직 재귀부분이 좀 약한 거 같아서 연습을 많이 해야겠다.