[백준] 17142 - 연구소3(Python)

문제 출처:

www.acmicpc.net/problem/17142

17142번: 연구소 3

문제 풀이:

• 삼성 기출은 대부분 BFS, DFS, 구현으로 끝나는 거처럼 이 문제 또한 구현이다.

• 핵심이 되는 부분은 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다."라고 쓰여있는 부분이라고 생각한다.

• 활성 바이러스가 비활성 바이러스가 있는 칸으로 넘어갈 때는 1초의 시간이 걸리지만 실제로 비활성 바이러스도 바이러스로 치기 때문에 비활성 바이러스를 굳이 활성화시키지 않아도 종료되는 케이스가 있다.

• 여기서 2가지 케이스로 나눠지는데 비활성 바이러스로 끝나는 케이스와 비활성 바이러스를 넘어서 계속 진행되어야 하는 경우이다. 여기서 좀 많이 헤매었다.

• 예시를 들어보자

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 2 0
1 1 1 1 1

이와 같은 케이스에서 (4,1)의 바이러스를 선택한 경우

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,0) 0 0 2 0
1 1 1 1 1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,0) (2,1) 0 2 0
1 1 1 1 1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,0) (2,1) (2,2) 2 0
1 1 1 1 1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,0) (2,1) (2,2) (2,3) 0
1 1 1 1 1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,0) (2,1) (2,2) (2,3) (2,4)
1 1 1 1 1

  와 같이 진행된다.

(4,4)를 선택하면

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 0 (2,0) 0
1 1 1 1 1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 0 (2,1) (2,0) (2,1)
1 1 1 1 1


5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 (2,2) (2,1) (2,0) (2,1)
1 1 1 1 1


만약에 더 진행한다면


5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,3) (2,2) (2,1) (2,0) (2,1)
1 1 1 1 1

이와 같이 진행되는데 우리는 2번째의 상황에서 종료를 해야 한다.

 

따라서 나는 진행하고자 하는 좌표의 값이 0인 경우는 진행을 하고 최종 cnt(답으로 쓰이는)을 업데이트하지만

비활성 바이러스인 경우는 최종 cnt는 업데이트를 해주지 않고 추후를 위해 마지막 단계처럼 해당 블록의 cnt만 업데이트하였다.

이처럼 따로 업데이트해주어야 하는 예제는 다음 예제를 보면 알 수 있다.

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 2 0 2 0
1 1 1 1 1
cnt=0

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 2 0 (2,0) 0
1 1 1 1 1
cnt=0

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 2 (2,1) (2,0) (2,1)
1 1 1 1 1
cnt=1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 (2,2) (2,1) (2,0) (2,1)
1 1 1 1 1
cnt=1

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
(2,3) (2,2) (2,1) (2,0) (2,1)
1 1 1 1 1
cnt=3

 

정답 코드 :

 

from collections import deque
#import numpy as np
from copy import deepcopy
from sys import stdin
from itertools import combinations

input = stdin.readline

n,m = map(int,input().split())
original_map = [list(map(int,input().split())) for _ in range(n)]
virus=[]
target_num =0

#virus_locate
for i in range(n):
    for j in range(n):
        if(original_map[i][j]==2):
            virus.append((i,j,0))
        elif(original_map[i][j]==0):
            target_num+=1

#virus_combinations
c_virus = list(combinations(virus,m))

def check_map():
    global n,maps
    for i in range(n):
        for j in range(n):
            if(maps[i][j]==0):
                return False
    return True


def bfs(active_virus):
    global n,maps,ans
    visited =[[0]*n for _ in range(n)]
    queue=deque()
    queue.extend(active_virus)
    for i in queue:
        i_,j_,qq = i
        visited[i_][j_]=1

    di = [1,0,-1,0]
    dj = [0,1,0,-1]
    cnt=0
    while(queue):
        ti,tj,tcnt = queue.popleft()
        for i in range(4):
            ni = ti+di[i]
            nj = tj+dj[i]
            if(ni>=0 and ni<n and nj<n and nj>=0):
                if(maps[ni][nj]!=1 and visited[ni][nj]==0):
                    visited[ni][nj]=1
                    if(maps[ni][nj]==0):
                        maps[ni][nj]=2
                        cnt = tcnt +1
                        if(cnt>ans):
                            break
                    queue.append((ni,nj,tcnt+1))

    return cnt


ans = 1e9
for i in c_virus:
    maps= deepcopy(original_map)
    res = bfs(i)
    if(check_map()):
        ans = min(res,ans)

print(ans if ans!=1e9 else -1)