[백준][Python][17142][시뮬레이션] 연구소 3

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

17142번: 연구소 3

 

시뮬레이션 문제다.

 

코드가 더러워 보이는데 더러운것 맞다.

 

이 문제는 모든 선택된 바이러스 조합에 대해 BFS를 통해 최솟값을 구하는 방식으로 풀었다.

 

우선 입력을 읽는데, 바이러스 위치는 따로 저장하고, 벽이 아닌 곳의 갯수는 bannum 을 통해 계산한다.

bannum = n*n - 바이러스 갯수 - 벽의 갯수.

이 bannum을 통해 바이러스가 모든 위치를 감염시켰는지를 검사한다.

 

그리고, 바이러스 중 m 개를 itertools.combinations를 통해 선택하고, 이를 BFS로 탐색한다.

BFS는 딱히 달라진건 없고, 벽이 아닌곳을 탐색하는 방식이다.

import sys
from collections import deque
from itertools import combinations,permutations

dx,dy = [1,-1,0,0],[0,0,1,-1]
n,m = [int(i) for i in sys.stdin.readline().split()]
d = []
vlist = []
bannum = n*n -m
for i in range(n):
    d.append([int(i) for i in sys.stdin.readline().split()])
    
for i in range(n):
    for j in range(n):
        if d[i][j]==2:
            vlist.append([i,j])
            #bannum-=1
        if d[i][j]==1:
            bannum-=1
         
ans = 9998999999999998989

def bfs(c):
    tmpans = 0
    cont = 0
    q = deque()
    m = [['-']*n for _ in range(n)]
    
    for cc in c:
        q.append(cc+[0])
        m[cc[0]][cc[1]]=0
        
    while q :
        cy,cx,cd = q.popleft()
        for i in range(4):
            ny,nx = cy+dy[i],cx+dx[i]
            if 0<=ny<n and  0<=nx<n:
                if m[ny][nx]=='-' and d[ny][nx]!=1:
                    m[ny][nx]=cd+1
                    q.append([ny,nx,cd+1])
                    if d[ny][nx]==0:
                        tmpans = max(tmpans,cd+1)
                    
                    cont+=1

    if cont == bannum:
        return tmpans
    else:
        return 9998999999999998989
        
for c in combinations(vlist, m):
    ans = min(bfs(c),ans)
    
if ans == 9998999999999998989:
    print(-1)
else:
    print(ans)