[Python/파이썬] 백준 14502 연구소 - (BFS + 백트래킹)

문제 설명

 

입력과 출력

 

입출력 예제

 

---

풀이 코드

 

풀이 핵심

1. 벽의 개수가 3개를 설치한 모든 2차원 배열(경우의 수)를 구한다.
2. 3개의 벽이 설치된 2차원 배열마다 bfs()로 탐색하여 가장 큰 안전지대 개수로 갱신한다.

 

정답 코드

pypy3로 제출하여야 시간초과 없이 통과

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)]
result = 0

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

# 백트래킹으로 3개의 벽을 설치한모든 조합을 만듬
def createWall(wall_cnt):
    if wall_cnt == 3:
        bfs()
        return
    for x in range(n):
        for y in range(m):
            if virus_map[x][y] == 0:
                virus_map[x][y] = 1
                createWall(wall_cnt + 1)
                virus_map[x][y] = 0 

# 바이러스 전파
def bfs(): 
    global result
    wall_Arr = copy.deepcopy(virus_map)
    q = deque()

    for x in range(n): # 바이러스의 위치 정보 큐에 저장
        for y in range(m):
            if wall_Arr[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_Arr[nx][ny] == 0:
                wall_Arr[nx][ny] = 2
                q.append((nx, ny))

    #안전지대 개수 카운팅
    safezone = 0 
    for line in wall_Arr:
        safezone += line.count(0)
    result = max(safezone, result)

createWall(0)
print(result)