[Python] 백준 14502번 : 연구소

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

14502번: 연구소

---

💡 문제 풀이

그래프 탐색 + 브루트 포스 문제이다.

 

벽을 단 3개만 설치해서 얻을 수 있는 최선의 경우를 찾아야 한다.

완전 탐색을 통해서 3개를 설치했을 때 발생하는 모든 경우를 따지고,

bfs를 사용해서 주어진 경우를 따져서 안전 구역의 개수를 따져주면 된다.

주의해야 할 점은 깊은 복사를 사용하지 않으면 원본이 훼손된다는 점이다!

✔️ 느낀 점

이렇게 따지는 경우를 어떻게 해야 할지 몰랐는데 단순하게 모두 따져보면 되었던 것이었다! 성장했다 ㅎㅎ

💻 코드

import sys
from copy import deepcopy
from collections import deque
input = sys.stdin.readline

moves = [(1,0), (0,1), (-1,0), (0,-1)]
MAX_WALL = 3

def countSafeZone(board):
    global safeZone
    cnt = 0
    
    for b in board:
        cnt += b.count(0)
    
    safeZone = max(safeZone, cnt)

def bfs(board):
    q = deque(givenVirus)
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + moves[i][0]
            ny = y + moves[i][1]
            
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
                board[nx][ny] = 2
                q.append([nx, ny])
                
    countSafeZone(board)

def arrangeWall(cnt):
    if cnt == MAX_WALL:
        bfs(deepcopy(board))
        return
    
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                board[i][j] = 1
                arrangeWall(cnt + 1)
                board[i][j] = 0

safeZone = 0
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

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

arrangeWall(0)
print(safeZone)