백준 17141번 연구소 2 (Python 3)

Baekjoon online judge 17141번 파이썬

 

링크

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

17141번: 연구소 2

combination을 이용해서 2번위치에 바이러스를 m개 놓을 수 있는게 가능한 조합을 찾는다.

zero_cnt를 이용해서 bfs가 끝났을 때, 모든 곳에 바이러스가 퍼졌는지 체크한다.

(바이러스가 놓이지 않은 2번도 zero_cnt에 포함해야한다.)

소스코드

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


index=[[1,0],[-1,0],[0,1],[0,-1]]
now_min=sys.maxsize

def bfs(virus_list,zero_cnt):
  global now_min
  queue=deque()
  visited=[[False for _ in range(n)] for _ in range(n)]
  for v in virus_list:
    vy,vx=v
    queue.append([vy,vx,0])
    visited[vy][vx]=True
    zero_cnt-=1

  while queue:
    y,x,cnt=queue.popleft()

    for indy,indx in index:
      ny=y+indy
      nx=x+indx

      if 0<=nx<n and 0<=ny<n and not visited[ny][nx] and map_data[ny][nx]!=1:
        visited[ny][nx]=True
        queue.append([ny,nx,cnt+1])
        zero_cnt-=1
  if zero_cnt==0:
    now_min=min(now_min,cnt)
    return



n,m=map(int,input().split())
map_data=[list(map(int,input().split())) for _ in range(n)]

zero_cnt=0
possible=[]
for i in range(n):
  for j in range(n):
    if map_data[i][j]==0:
      zero_cnt+=1
    elif map_data[i][j]==2:
      possible.append([i,j])
      zero_cnt+=1
      map_data[i][j]=0

comb=combinations(possible,m)

for c in comb:
  bfs(c,zero_cnt)

if now_min==sys.maxsize:
  print(-1)
else:
  print(now_min)