[백준] 17141 연구소 2 Python

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

17141번: 연구소 2

BFS + 브루트포스로 풀었다

비트마스킹으로도 풀 수 있는 것 같은데 연습해야겠다..

import sys
from itertools import combinations
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]
answer = int(1e9)
virus_available = [] # 바이러스 놓을 수 있는 칸

for i in range(N):
    for j in range(N):
        if array[i][j] == 2:
            virus_available.append([i, j])

# 조합으로 가능한 바이러스 배치 모든 경우를 brute force로 구함, 최솟값 갱신
# 탐색은 bfs 사용함
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(virus_start):
    time_count = 0
    queue = deque([])
    visited = [[False] * N for _ in range(N)]
    for a, b in virus_start:
        queue.append((a, b, 0))
        visited[a][b] = True 
    while queue:
        x, y, t_count = queue.popleft()
        time_count = max(time_count, t_count)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == False and array[nx][ny] != 1:
                    queue.append((nx, ny, t_count+1))
                    visited[nx][ny] = True 



    for i in range(N):
        for j in range(N):
            if array[i][j] != 1 and visited[i][j] == False: # 0 또는 2 인데 아직 방문 안 한 칸이 있는 경우
                return int(1e9)
    return time_count


for virus_start in combinations(virus_available, M):
    answer = min(answer, bfs(virus_start))

if answer == int(1e9):
    print(-1)
else:
    print(answer)