[Python] 백준 - 연구소

import sys
import copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline

def bfs():

    for i in combinations(blank, 3): # 빈 칸 위치중에 3개 combination 조합 만들어내기
        queue = deque() # 큐 생성
        trial = copy.deepcopy(grid) # 배열 복사해두기

        for y, x in i: # 빈 칸 생성!
            trial[y][x] = 1

        for i in range(len(virus)): # 바이러스 큐에 담기
            queue.append(virus[i]) 

        while queue:
            y, x = queue.popleft() # 들어온 바이러스 순서대로 popleft()

            for i in range(4): # 위, 아래, 왼, 오 위치 설정
                ny = dy[i] + y
                nx = dx[i] + x

                if ny <= -1 or ny >= n or nx <= -1 or nx >= m: #설정한 위치가 벗어났을 경우 X
                    continue
                if trial[ny][nx] == 0: # 벗어난 범위 아닐 경우, 빈칸일 경우, 바이러스 발사.
                    trial[ny][nx] = 2
                    queue.append([ny, nx]) # 바이러스 담기

        global safe # 답이 될 값. 0의 개수가 가장 큰 경우를 확인
        safe_current = 0 # 0의 개수 셀 변수

        for i in range(n): # 0의 개수 카운트
            safe_current += trial[i].count(0) 

        safe = max(safe, safe_current)


n, m = map(int, input().split())
grid = [] # 모든 값을 담는 배열
virus = [] # 바이러스 위치를 담는 배열
blank = [] # 빈 칸 위치를 담는 배열
safe = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    grid.append(list(map(int, input().split())))

for y in range(n):
    for x in range(m):
        if grid[y][x] == 2:
            virus.append([y, x])
        if grid[y][x] == 0:
            blank.append([y, x])

bfs()
print(safe)

 

 

입력받을 배열
바이러스 위치를 담는 배열
빈 칸 위치를 담는 배열

 

 

이렇게 3개를 준비한다.

 

1. 입력받기 

2. 바이러스 배열 or 빈 칸 배열 확인해서 append 하기

3. bfs 실행

- 빈 칸 배열 중에 3개 combination 사용해서 3개 뽑아서 중복 허용 조합 만들기 -> 해당 조합 벽으로 설정

- 벽으로 설정 후, virus를 차례대로 큐에 담는다.

- 큐가 없어질 때까지 ~ virus에 있는 값을 순서대로 popleft()한다 그 바이러스에 해당하는 왼, 오, 위, 아래 방향 설정해서 그 바이러스 발사. 그리고 바이러스 담기를 실행.

- 큐가 이제 다 없어졌다면, 확인을 해야할 차례. (바이러스 전염이 끝난 직후)

- 0인 공간(감염되지 않은 공간)의 개수를 센다.

- 그 중에서 가장 큰 개수를 print...

 

 

https://clap0107.tistory.com/11

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

 

 

이 분의 코드를 참고하였다. 짱 !