[백준_17141] 연구소 2 python

bfs를 동시에 돌릴 줄 알아야 한다는 점과,

백트랙킹을 통해 바이러스를 놓는 조합을 모두 구해야 하는 점,

그리고 모든 바이러스가 이미 퍼져있는 상황을 판단하는 점 등이 중요했던 것 같다.

# 입력 속도 개선
import sys
input = sys.stdin.readline

# n, m 입력
n, m = map(int, input().split())

# lab 입력
lab = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# all_done()
def all_done():
    # 바이러스를 놓을 수 있는 위치의 수와 m이 다르면,
    if len(possible_virus_pos) != m:
        # 실패
        return False
    # lab 돌면서
    for i in range(n):
        for j in range(n):
            # 빈칸을 발견하면,
            if lab[i][j] == 0:
                # 실패
                return False
    # 다 돌았는데 빈칸 없으면 성공
    return True

# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# can_spread(x, y)
def can_spread(x, y):
    # 범위 내에 있고, 방문한 적 없고, 벽이 아니면 가능
    return in_range(x, y) and not visited[x][y] and lab[x][y] != 1

# bfs()
def bfs():
    while q:
        x, y = q.popleft()
        dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            # 퍼질 수 있으면,
            if can_spread(nx, ny):
                # 큐에 넣어주고
                q.append((nx, ny))
                # 방문 처리 해 주고
                visited[nx][ny] = 1
                # step 배열 관리
                step[nx][ny] = step[x][y] + 1

# simulate()
def simulate():
    # 전역 변수 선언
    global visited, step

    # visited 선언 및 초기화
    visited = [
        [0] * n
        for _ in range(n)
    ]

    # step 선언 및 초기화
    step = [
        [0] * n
        for _ in range(n)
    ]

    # 선택된 위치들을 뽑아,
    for vx, vy in selected_virus_pos:
        # 큐에 넣어주고
        q.append((vx, vy))
        # 방문 표시 해 주기
        visited[vx][vy] = 1
    
    # 다 넣었으면 bfs
    bfs()

    # 시뮬레이션 실패 여부 확인
    for i in range(n):
        for j in range(n):
            # 연구실이 빈칸인데 방문못한 칸이 있으면,
            if lab[i][j] == 0 and not visited[i][j]:
                # 실패
                return False
    
    # 현재 케이스에 대한 시간값 설정
    curr_ans = 0

    # step 배열 돌면서
    for i in range(n):
        for j in range(n):
            # 최댓값 갱신
            if step[i][j] > curr_ans:
                curr_ans = step[i][j]
    
    # 반환
    return curr_ans

# 설계
# 바이러스를 둘 수 있는 좌표를 넣어 줄 리스트
possible_virus_pos = []

# lab 돌면서
for i in range(n):
    for j in range(n):
        # 바이러스를 놓을 수 있는 위치를 발견하면,
        if lab[i][j] == 2:
            # 좌표를 기록
            possible_virus_pos.append((i, j))

# 선택된 좌표를 기록해 줄 리스트
selected_virus_pos = []

# ans 설정
ans = sys.maxsize

# 큐 사용 준비
from collections import deque
q = deque()

# m개 좌표 선택해 줄 함수
def select_virus_pos(curr_idx, cnt):
    # 전역 변수 선언
    global ans

    # 종료 조건
    if cnt == m:
        # 시뮬레이션이 성공하면(바이러스가 다 퍼졌으면),
        if simulate():
            # 최솟값 교체
            ans = min(ans, simulate())
        return
    if curr_idx == len(possible_virus_pos):
        return
    
    # 넣어주기
    selected_virus_pos.append(possible_virus_pos[curr_idx])
    select_virus_pos(curr_idx + 1, cnt + 1)
    selected_virus_pos.pop()

    select_virus_pos(curr_idx + 1, cnt)

# 함수 호출
select_virus_pos(0, 0)

# 처음부터 바이러스가 다 퍼져있는 상황이라면,
if all_done():
    # 0초만에 해결
    print(0)
# 모든 시뮬레이션이 다 실패했다면,
elif ans == sys.maxsize:
    # -1 출력
    print(-1)
# 시뮬레이션이 한번이라도 성공했다면,
else:
    # 답 출력
    print(ans)