[삼성SW역량][Python/BOJ] 백준 17142 연구소3(BFS)

 

벽의 개수와 바이러스의 공간을 list로 저장한다.

 

 

combinations를 이용해 활성화시킬 m개의 바이러스를 선택한다. 

bfs를 이용해 모든 빈곳을 감염시키는 시간을 반환하도록 한다. 

 

 

 

< bfs 함수 설명 >

0. time 변수 생성 

1. vis 배열을 만든다. 

2. 바이러스를 deque에 넣고 바이러스의 위치는 vis의 값을 0으로 설정한다.

3. 바이러스가 퍼진다. 

    3-1. 퍼지는 곳이 빈곳이라면 퍼지고, time 을 갱신 

    3-2. 퍼지는 곳이 비활성화된 바이러스라면 활성화시킨다. 

4. 미리 구해놓은 벽의 개수화 현재 벽의 개수를 비교한다. 

5. 만약 다르면 모든 빈곳을 채우지 못한것이므로  무한대를 반환, 아니라면 time 을 반환 

 

 

 

 

 

 

코드 : 

from collections import deque
from itertools import combinations as c 


dx = [1,0,-1,0] 
dy = [0,-1,0,1]



def bfs(active) :
    time = 0
    vis = [[-1] *n for _ in range(n)] # 바이러스 자리와  평범한 자리를 비교하기위해 -1로 초기화 
    q = deque()
    
    for i,j in active :
        q.append([i,j])
        vis[i][j] = 0 # 여기서부터 바이러스가 퍼져나감 
    
    while q :
        x,y = q.popleft()
        for k in range(4) :
            nx,ny = x + dx[k], y + dy[k]
            if 0<=nx<n and 0<=ny<n and vis[nx][ny] == -1:
                if mp[nx][ny] == 0 : #  아무것도 없을 경우 
                    q.append([nx,ny]) 
                    vis[nx][ny] = vis[x][y] +1
                    time = max(time, vis[nx][ny]) # 시간갱신 
                if mp[nx][ny] == 2 : # 비활성화된 바이러스일 경우 
                    q.append([nx,ny])
                    vis[nx][ny] = vis[x][y] +1 
                    # 아무것도 없는 곳으로  바이러스가 퍼져나간것이 아니라 바이러스의 활성화 이므로 시간 갱신 안함 
    if sum(vis,[]).count(-1) != wall_cnt : return int(1e9) 
    # 현재 벽의 개수와 원래 벽의 개수를 비교 
    # 다르면 원래상태보다 벽이 많다 ? -> 빈곳인데 바이러스가 안퍼진곳이 있다. 

    return time 
                    
                    
if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for i in range(n)]


    wall_cnt = 0
    candidate = []
    for i in range(n) :
        for j in range(n) :
            if mp[i][j] == 1 : # 벽이라면 
                wall_cnt+=1 
            elif mp[i][j] == 2 : # 바이러스라면 
                candidate.append([i,j])
    ans = int(1e9)
    for active in c(candidate,m) :
        ans = min(ans,bfs(active))
    print(ans if ans < int(1e9) else -1)

 

 

 

 

벽의 개수를 셀 때 

 

if sum([list(vis[i]).count(-1) for i in range(n)]) == wall_cnt :
        return time

이렇게 할 수도 있다. 

 

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@ms269/%EB%B0%B1%EC%A4%80-17142-%EC%97%B0%EA%B5%AC%EC%86%8C-3-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python

[백준] #17142 - 연구소 3 (파이썬, Python)