[백준 14502번] 연구소 - Python으로 구현하기

[백준 14502번] 연구소 - Python으로 구현하기

 

문제 접근

• 바이러스의 확산 => BFS 알고리즘
• 벽을 세울 수 있는 경우의수 => itertools 모듈의 combinations, product
• 안전영역 확인 => chain, counter 모듈
• 메모리 효율성 문제로 제너레이터로 combinations 구현

 

생각해볼 점

• itertools 모듈 안쓰고 경우의수 어떻게 뽑으면 좋을지?
• copy 모듈을 이용하여 마지막 원상 복귀 코드 없애기

 

오답 분석

• 항상 불필요한 로직이 없는지 확인하기

 

# 연구소
import sys
input = lambda:sys.stdin.readline().rstrip()

from itertools import product,chain,combinations as cm
from collections import deque,Counter

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

dq=deque()
di =[[-1,0],[0,-1],[1,0],[0,1]] # 4방향
max_cnt=0

for wall in cm(list(product(range(n),range(m))),3):
    return_wall=True
    for w in wall:
        x,y=w
        if a[x][y]==1 or a[x][y]==2:    # 벽을 둘 수 없는 자리
            return_wall=False
            break
    if not return_wall: continue    # 벽 3개를 설치 못한 경우
    else:
        for w in wall:  # 벽 설치
            x,y=w
            a[x][y]=1

    # 바이러스들 deque에 삽입
    for i in range(n):
        for j in range(m):
            if a[i][j]==2:
                dq.append([i,j])

    # bfs
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]
            if 0<=nx<n and 0<=ny<m and a[nx][ny]==0:
                dq.append([nx,ny])
                a[nx][ny]=-1

    c=Counter(chain(*a))    # 2차원 맵 -> 1차원 맵
    max_cnt=max(max_cnt,c[0])   # 0의 개수

    # 기존 맵으로 원상복귀
    for w in wall:
        x,y=w
        a[x][y]=0
    for i in range(n):
        for j in range(m):
            if a[i][j]==-1:
                a[i][j]=0
print(max_cnt)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!