17142-python풀이

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

17142번: 연구소 3

문제를 읽고 두가지가 생각났다.

1. 어디에 바이러스를 심어놔야 제일 빠르게 될까

2. BFS를 이용해 좌우상하로 전염시켜 시간을 구하자.

그래서 바이러스를 놓을 수 있는 모든 조합을 구해준 후 BFS를 통해 시간이 더 최소인 것을 구하기로 했다.

BFS함수에서 visited 이차배열로 한번에 감염을 시키면 1씩 이전값에서 증가하도록 count까지 해주었다. 

마지막까지 감염시키는데 몇초걸리는지 알기 위해 if문을 들어가고 만약 그래프값이 0이라면 새로 감염이 된것이기에 max로 계속 temptim을 비교해주었다.

모두 돌고 나서도 visited이차배열에 -1이 있다면 그것은 벽이여야 한다. 만약 그렇지 않다면 이것은 전부 전염하는데 실패한 것이므로 -1을 출력해주어야 한다.

맨 마지막에 min값으로 비교해주기에 만약 실패한 경우는 sys.maxsize로 

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline
N,M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
virus=[]
wall = 0 #벽갯수
#바이러스놈의 위치와 벽개수부터 찾자       
for i in range(N):
    for j in range(N):
        if(graph[i][j] == 2):
            virus.append((i,j))
        elif graph[i][j] == 1 :
            wall += 1
def BFS(virusdata):
    q = deque()
    
    visited = [[-1]* N for _ in range(N)] #일단 -1로 세팅
    temp = 0
    cnt = 0
    for x,y in virusdata:
        q.append((x,y))
        visited[x][y] = 0 # 활성화된 애들은 일단 방문했으니
    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 < N and visited[nx][ny] == -1 and graph[nx][ny] != 1): #방문안한놈들 + 벽이 아닌곳만 가자
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx,ny))
                if(graph[nx][ny]==0):
                    temp = max(temp, visited[nx][ny]) 
    for row in visited:
        for element in row:
            if element == -1:
                cnt += 1
    if cnt != wall:
        return sys.maxsize
    return temp
                
                
ans = sys.maxsize                
for virusdata in list(combinations(virus, M)):
    ans = min(BFS(virusdata), ans)
if(ans == sys.maxsize):
    print(-1)
else:
    print(ans)