백준 - 14502

dfs혹은 bfs로 풀거나 아니면 다른 해결 방법도 많은 것 같은 문제이다. 나는 bfs를 썼지만 뭔가 구현문제 같기도 했다.

#p341

from itertools import combinations
import sys
import copy
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
maps = []
spaces = []
viruses = []

for i in range(n):
    maps.append(list(map(int, input().split())))

#빈 공간의 좌표 구함
for x in range(n):
    for y in range(m):
        if maps[x][y] == 0:
            spaces.append((x, y))
        elif maps[x][y] == 2:
            viruses.append((x, y))

max_total = 0

#빈 공간에 경우의 수만큼 기둥을 박은 것을 확인하여 최대 안전구역 도출
for a in list(combinations(spaces, 3)):
    spaces_temp = copy.deepcopy(maps)
    for b in a:
        spaces_temp[b[0]][b[1]] = 1 #기둥 박기
    #BFS
    queue = deque(viruses)
    while queue:
        start = queue.popleft()
        if start[0] - 1 >= 0:
            if spaces_temp[start[0] - 1][start[1]] == 0:
                spaces_temp[start[0] - 1][start[1]] = 2
                queue.append((start[0] - 1, start[1]))
        if start[0] + 1 < n:
            if spaces_temp[start[0] + 1][start[1]] == 0:
                spaces_temp[start[0] + 1][start[1]] = 2
                queue.append((start[0] + 1, start[1]))
        if start[1] - 1 >= 0:
            if spaces_temp[start[0]][start[1] - 1] == 0:
                spaces_temp[start[0]][start[1] - 1] = 2
                queue.append((start[0], start[1] - 1))
        if start[1] + 1 < m:
            if spaces_temp[start[0]][start[1] + 1] == 0:
                spaces_temp[start[0]][start[1] + 1] = 2
                queue.append((start[0], start[1] + 1))
            
    total = 0
    for i in spaces_temp:
        for j in i:
            if j == 0:
                total += 1
    if total > max_total:
        max_total = total
        
print(max_total)

반성할 점은 또 문제 조건을 제대로 보지도 않고 고민하고 있었다는 점이다. 일단 기둥 세 개를 박은 모든 경우의 수를 봐야하는데 이때 조합을 신경쓰지 않고 구현하다가 시간을 허비했다. 수능 수학 풀 때처럼 문제 먼저 읽어야하는데 아직 습관화가 덜 된 것 같다... 그리고 좌표를 계산하여 업데이트 하는 if문 두 개가 중첩되어 있는 코드는 분명 간결하게 쓸 수 있는데 너무 더럽게 쓴 것 같다. 다른 사람들이 자주 쓰듯이 dx = [0, 1, 0, -1], dy = [1, 0, -1, 0]으로 놓고 깔끔하게 써야겠다.