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

문제

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

 

풀이

아직 bfs 에 익숙치 않고 이번에도 큐에 넣는걸 생각을 못했다...

make_wall까지는 했는데 bfs 구현을 어떻게 해야할지 모르겠어서 구글링을 통해서 참고해서 풀었다.

 

코드

from collections import deque
import sys
import copy

input = sys.stdin.readline

n, m = map(int, input().split()) # 행, 열
virus_map = [list(map(int, input().split())) for _ in range(n)]
answer = 0

dx= [1, -1, 0, 0]
dy= [0, 0, -1, 1]

def make_wall(wall_cnt):
    if wall_cnt == 3 : # 이미 3개 생성했다면 bfs() 실행
        bfs()
        return
    for x in range(n):
        for y in range(m):
            if virus_map[x][y]==0 :
                virus_map[x][y]=1
                make_wall(wall_cnt+1)
                virus_map[x][y]=0

def bfs():
    global answer
    wall = copy.deepcopy(virus_map)
    q = deque() # 바이러스 위치 정보 저장용 큐
    for x in range(n):
        for y in range(m):
            if wall[x][y]==2:
                q.append((x,y))
    while q :
        x, y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n and 0<=ny<m and wall[nx][ny]==0:
                wall[nx][ny]=2
                q.append((nx,ny))

    safe = 0 # 안전지대 개수
    for i in wall :
        safe += i.count(0)
    answer = max(safe, answer)

make_wall(0)
print(answer)