[백준] 14502 연구소

📖 문제

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

💻 내 코드

import sys
from collections import deque

dx=[-1,1,0,0]
dy=[0,0,-1,1]
res=0
n, m = map(int, sys.stdin.readline().split())

board = []
for i in range(n):
    board.append(list(map(int, sys.stdin.readline().split())))

brd=[[0]*m for _ in range(n)]

queue = deque([])

wall=[]
for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            wall.append([i,j]) # 빈칸의 위치 저장

def bfs():
    global res

    for i in range(n):
        for j in range(m):
            brd[i][j] = board[i][j] # 원본 배열 복사

    for i in range(3): 
    	# 저장된 3개의 빈칸의 위치에 벽 세우기
        brd[selected[i][0]][selected[i][1]] = 1

    for i in range(n):
        for j in range(m):
            if brd[i][j]==2:
                queue.append((i,j))

    while queue: 
    	#bfs를 통해 바이러스 퍼져 나갈 수 있는 곳 확인 후 2로 변경
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if brd[nx][ny] == 0:
                    brd[nx][ny] = 2
                    queue.append((nx, ny))

    total=0

    for i in range(n): # 빈칸(안전 영역)의 개수 세기
        for j in range(m):
            if brd[i][j]==0:
                total+=1
    res=max(res, total)


selected=[[0] for _ in range(3)]


def setWall(cnt, start): # 빈칸 3개를 골라 위치 저장(조합)
    if cnt==3:
        bfs()
        return

    for i in range(start, len(wall)):
        selected[cnt]=wall[i]
        setWall(cnt+1, i+1)

setWall(0, 0)


print(res)

💡 풀이

• 빈칸의 위치를 저장해둔 뒤, 조합을 이용해 3개 선택 가능한 모든 경우의 수 저장
• 저장된 위치에 벽 세우기
• 벽이 새로 세워진 상태로 바이러스가 퍼져나가는 것 확인
  • bfs를 이용하여 2가 있는 곳 주변에 0이 있다면 2로 변경
  • 퍼져나간 2에서도 계속 확인
• 모든 바이러스가 퍼진 후의 안전 영역 개수 확인
• 조합된 벽을 세울 수 있는 모든 위치에서 확인