[python] 백준 boj14502 연구소

1. 문제 요약

연구소 🟡4

 

N x M 크기의 연구소에서 3개의 벽(1)으로 바이러스(2)로부터의 안전 영역(0) 최댓값 구하기

 

2. 설계

BRUTE FORCE

브루트 포스로 벽을 세운 후,

BFS를 통해 바이러스 감염을 시키고

안전 영역 갯수 세기

 

3. 최종코드

from itertools import combinations
from copy import deepcopy
from collections import deque

#상, 우, 하, 좌
dr, dc = [-1, 0, 1, 0], [0, 1, 0, -1]

# 세로, 가로
N, M = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(N)]

blanks = []
viruses = []
for n in range(N):
    for m in range(M):
        if not lab[n][m]:
            blanks.append((n, m))
        if lab[n][m] == 2:
            viruses.append((n, m))

max_safe = 0
comb_walls = combinations(blanks, 3)

for walls in comb_walls:
    new_lab = deepcopy(lab)
    for wall in walls:
        y, x = wall
        new_lab[y][x] = 1

    q = deque()
    q.extend(viruses)
    while q:
        y, x = q.popleft()
        for d in range(4):
            ny = y + dr[d]
            nx = x + dc[d]
            if 0 <= ny < N and 0 <= nx < M and not new_lab[ny][nx]:
                new_lab[ny][nx] = 2
                q.append((ny, nx))

    safe = 0
    for nn in range(N):
        for mm in range(M):
            if not new_lab[nn][mm]:
                safe += 1

    if safe > max_safe:
        max_safe = safe

print(max_safe)

 

4. 느낀점

이것이 코딩테스트다 파이썬 기출 문제였다.

아직 시간 복잡도를 계산하는 데 익숙하지 않아서

어떤 문제에 완전 탐색을 적용해도 되고 아닌지 감이 없다 😣

 

이번 문제 역시 감히 완전탐색을 할 생각이 없었는데

너무 막막해서 해답의 구현 설명만 읽었더니 감이 와서 풀 수 있었다.

이제 약간 알고리즘 문제에 체계적으로 접근할 마음이 생겼다 (?)

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 좀 늦은 것 같긴 하지만