[Python] 백준 14502: 연구소

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

14502번: 연구소

Logic

wall이라는 함수를 돌면서 3개의 벽을 세운다. 벽을 세우는 데에는 벽의 숫자 외에 특정 조건이 존재하지 않으니 벽의 숫자가 3개가 될 때까지 벽을 세워주고... 벽이 다 세워졌으면 bfs 함수를 돈다! 마지막으로 안전 구역의 숫자를 세주면 끝!

과연 벽의 숫자를 다 세주는게 맞을까? 과연? 이라는 생각을 했으나 맞았다. 최적화는 둘째 문제고 일단 Brute-Force로 냅다 구현 먼저 하는 습관을 가지자... 그러면서 배우는 거지

일단 문제의 스케일을 먼저 확인한 후 전략을 세우는 습관을 가지자. N과 M이 충분히 작아서 Brute-Force로 충분히 풀리는 문제.

 

ANS

from collections import deque
import copy
dir = [(0,-1),(0,1),(-1,0),(1,0)]

def bfs():
    q = deque()
    sample = copy.deepcopy(arr)
    for i in range(N):
        for j in range(M):
            if sample[i][j] == 2:
                q.append((i,j))
    while q:
        r,c = q.popleft()
        for k in range(4):
            nr = r + dir[k][0]
            nc = c + dir[k][1]
            if 0<=nr<N and 0<=nc<M:
                if sample[nr][nc] == 0:
                    sample[nr][nc] = 2
                    q.append((nr,nc))
    global res
    cnt = 0
    for i in range(N):
        for k in range(M):
            if sample[i][k] == 0:
                cnt += 1
    res.append(cnt)


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
                wall(cnt+1)
                arr[i][j] = 0

N,M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
res = []
wall(0)
print(max(res))