백준/ Gold 4 문제 , 백준 파이썬 17142 , 연구소 3 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 17142 , 연구소 3 [BFS]

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
비활성화인 바이러스도 만나게 되면 활성화되게 하는 부분을 처음에 놓쳤었음.
이 문제를 보고 바로 조합이 떠올랐는데 조합을 쓰는 문제가 맞았다.

 

문제 출처

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

17142번: 연구소 3

 

 

 

풀이

 

 

 

1. 기본세팅

 

 

1. deque 선언 

 

2. 이 풀이에선 deepcopy 를 사용하기 때문에 deepcopy import 하기 (원래 리스트 보존 위함.)

 

3. 조합 사용 => combinations 사용

 

 

N, M 입력 받기   (주의! N행 M열 아님!! N행 N열임.)

 

bfs 호출시 리턴값들을 저장하기 위해서 check 리스트 선언

 

 

 

2. BFS

 

 

조금 까다로워 보일 수도 있다.

 

찬찬히 살펴보면

 

1. 우선 얼마만에 퍼지느냐를 체크해줄 cnt 변수

 

2. 여러번의 bfs 호출로부터 기존 MAP 리스트를 보존하기 위해 deepcopy 선언

 

3. 호출시 전달된 LIST 에 담긴 값들을 dq에 넣어주고 deepcopy 한 리스트에 표시해주기

 

4. 이후 dq 돌리기

 

5. 다른 bfs 문제들과 동일하게 돌리면서 저장되는 값들중 가장 큰값을 cnt와 비교해가며 cnt에 저장.

 

6. 만약 비활성화상태인 바이러스를 만나면 이전 단계 값 +1 로 해주고 dq에 넣어주기

    => 즉 0을 만나는것과 동일하게 감. 

    => 다른 점은 굳이 cnt를 비활성화인 바이러스를 만날때도 체크해줄 필요가 없음.

 

7. 이후 완성된 virusMAP에서 0 이 남아 있는지 확인 

    => 0 이 남아있다면 아무리퍼트려도 퍼지지 않는 구조이기 때문에 구했던 cnt 값 무시하고 -1로 바꿔서 리턴해버림.

 

 

3. 반례 대비

예제 7 과 같이 0이 초기부터 하나도 없는 경우를 걸러내기 위해 for 문을 돌려줌.

 

이때 check=True가 되지 않고 다돌았는데도 여전히 False라면 리스트에 0이 없는 상황.

 

이때는 0을 출력시키고 프로그램 종료

 

 

 

4. bfs 호출 및 리턴 값 처리

 

초기에 0이없는경우는 else 로 가서 0 출력 후 종료

 

0이 하나라도 있는 경우 이제 virus에 담긴 값을 조합 하여 추출

 

조합으로 만들어진 LIST를 하나씩 bfs 에 넣어 호출 시킴.

 

리턴 받은 값들은 result 리스트에 담아줌.

 

 

이후 remove_set을 사용해

 

result 에 담긴 -1들을 다 지워줌.

 

만약 -1을 다 지웠는데, result 에 담긴 값이 없다?

 

모든 조합의 경우들이 바이러스가 다 안퍼진 경우이므로 -1을 출력시키고 프로그램 종료

 

만약 result에 한 개 이상의 값들이 남아있는 경우는 다 퍼진 경우가 한 번 이상 존재하는 경우이므로 이 남은 값들 중에서

 

최솟값을 출력 시키면 출력시킬 정답이다.

 

 

 

 

정답

 

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

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

N,M=map(int,input().split())
MAP=[list(map(int,input().split())) for _ in range(N)]
check=[]
dq=deque()

def bfs(LIST,MAP):
    cnt=0
    virusMAP=deepcopy(MAP)
    for i in range(len(LIST)):
        dq.append(LIST[i])
        virusMAP[LIST[i][0]][LIST[i][1]]=1
    while dq:
        x,y=dq.popleft()
        for i in range(4):
            X,Y=x+vertical[i], y+parallel[i]
            if 0<=X<N and 0<=Y<N:
                if virusMAP[X][Y]==0:
                    dq.append([X,Y])
                    virusMAP[X][Y]=virusMAP[x][y]+1          
                    if cnt<virusMAP[X][Y]:
                        cnt=virusMAP[X][Y]
                elif virusMAP[X][Y]=='*':
                    dq.append([X,Y])
                    virusMAP[X][Y]=virusMAP[x][y]+1  
                    
    for i in range(N):
        for j in range(N):
            if virusMAP[i][j]==0:
                cnt=-1
    return cnt   

virus=[]
check=False
for i in range(N):
    for j in range(N):
        if MAP[i][j]==2:
            virus.append([i,j]) 
            MAP[i][j]='*'
        if MAP[i][j]==0:
            check=True

if check==True:
    result=[]
    LIST=list(combinations(virus,M))
    for i in range(len(LIST)):
        result.append(bfs(LIST[i], MAP))

    remove_set={-1}
    if -1 in result:
        result=[i for i in result if i not in remove_set]
        if len(result)==0:
            print(-1)
            exit(0)

    print(min(result)-1)
else:
    print(0)