[Python] 백준 14502번 문제, 연구소

<문제 링크>

 

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

14502번: 연구소

 

---

<풀이>

 

연구소 정보(0: 빈 칸, 1: 벽, 2: 바이러스)가 주어지고

벽을 세 개 세웠을 때, 바이러스가 없는 안전한 빈 칸의 갯수를 구하는 문제이다.

 

브루트포스 알고리즘이기 때문에 벽을 세 개 놓을 수 있는 모든 경우를 돌며

BFS를 통해 바이러스를 전파시킨 다음에

전파가 끝난 다음에 빈 칸의 갯수를 세어 최대값만을 구한다.

 

벽을 세 개 놓을 수 있는 모든 경우는 [0][j]부터 [N-1][M-1]까지 탐색하면서 0일 경우에 벽을 세울 수 있기 때문에 create_wall()를 호출한다.

create_wall에서 벽의 갯수를 세는데 3개가 됐을 경우 BFS를 작동시키고

다음 3개가 될 경우를 찾는다.

 

핵심은 깊은 복사인 것 같다.

LIST.copy()는 얕은 복사를 수행해 arr나 copy_arr에 값 변경이 생긴다면 board에 영향을 끼치지만,

import copy를 통해 라이브러리를 import하고 copy.deepcopy(리스트)를 통해 깊은 복사 형태로 반환한다.

 

---

<코드>

board[][]: 연구소 정보

virus_position[]: 튜플 형식으로 바이러스 위치 저장

move[]: 상하좌우 이동

result: 안전 영역 최대 크기

arr[][]: 가정으로 벽을 세울 연구소 정보(board를 깊은 복사)

copy_arr[][]: 바이러스 전파된 연구소 정보

---

import sys
import copy


def bfs():
    global result, virus_position
    count = 0 # 현재 경우의 빈 칸 개수
    que = virus_position.copy()
    copy_arr = copy.deepcopy(arr)
    
    # 바이러스 BFS 전파
    while que:
        x, y = que.pop(0) # 바이러스 위치 받아오기

        for i, j in move:
            dx = x + i
            dy = y + j
            
            if 0 <= dx < N and 0 <= dy < M: # 주위에
                if copy_arr[dx][dy] == 0: # 빈 칸이 있다면
                    copy_arr[dx][dy] = 2 # 바이러스 전파
                    que.append((dx, dy))

    # 빈 칸 세기
    for i in range(N):
        count += copy_arr[i].count(0)
    
    # 값 비교
    result = max(result, count)

def create_wall(count, x):
    if count == 3: # 벽 다 세웠으니 바이러스 전파
        bfs()
        return

    # 벽 세우기
    for i in range(x, N):
        for j in range(M):
            if arr[i][j] == 0:
                arr[i][j] = 1
                create_wall(count+1, i)
                arr[i][j] = 0


if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = []
    virus_position = []
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
    result = 0 # 안전 영역의 최대 크기

    # input
    for i in range(N):
        board.append(list(map(int, sys.stdin.readline().rstrip().split())))

        # 바이러스 좌표값 기억
        for j in range(M):
            if board[i][j] == 2:
                virus_position.append((i, j))

    for i in range(N):
        for j in range(M):
            # 벽 세우기
            if board[i][j] == 0:
                arr = copy.deepcopy(board)
                
                arr[i][j] = 1
                create_wall(1, i)
                arr[i][j] = 0

    print(result)