[BOJ/백준] 17142 연구소3

from itertools import combinations
from collections import deque
def bfs(active_virus,total_virus):
    global result,virus_list,N
    virus_cnt = 0
    deactive_virus = virus_list-active_virus
    stack = deque()
    spend_time = [row[:] for row in spend_time_stand]
    for x,y in active_virus:
        stack.append((x,y,0))
        spend_time[x][y] = 0
        virus_cnt += 1
    min_time = -1
    while stack:
        x,y,time = stack.popleft()
        if min_time > result:
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if spend_time[nx][ny] == -1 and (nx,ny) not in wall_list:
                    if (nx,ny) not in deactive_virus:
                        spend_time[nx][ny] = time+1
                        stack.append((nx,ny,time+1))
                        min_time = spend_time[nx][ny]
                        virus_cnt += 1
                    else:
                        spend_time[nx][ny] = 0
                        stack.append((nx,ny,time+1))
                        

        
    if total_virus == virus_cnt:
        if result >min_time and min_time != -1:
            result = min_time


    



N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,1,-1]
arr = [list(map(int,input().split())) for _ in range(N)]
virus_list = set()
wall_list = set()
total_virus = N*N
spend_time_stand = [[-1] *N for _ in range(N)]
for x in range(N):
    for y in range(N):
        if arr[x][y] == 2:
            virus_list.add((x,y))
        elif arr[x][y] == 1:
            wall_list.add((x,y))
            total_virus -= 1

start_virus_list = combinations(virus_list,M)
result = float('inf')
if total_virus-len(virus_list)+M != M:
    for lists in start_virus_list:
        bfs(set(lists),total_virus-len(virus_list)+M)
else:
    result = 0

if result == float('inf'):
    print(-1)
else:
    print(result)

연구소 시리즈 문제 중 3번 문제이다. 여기서는 예외로 해야할 곳이 생각외로 많아서 많이 틀리면서 푼 문제이다.

 

문제 자체를 이해하자면, 처음부터 있는 바이러스들이 존재한다.

그런데 여기서 M개의 바이러스가 활성화 되고, 나머지 바이러스는 비활성 상태가 된다.

 

활성 바이러스가 비활성 바이러스 가면 활성화 상태가 된다.

 

여기서 주의해야할 점은 이 점이다. 처음부터 있는 바이러스는 비활성 상태지만 이미 뿌려진 상태이기 때문에, 비활성->활성이 될뿐이지, 이미 바이러스가 존재하기 때문에, 퍼트리는데 드는 시간에는 포함이 되지 않는다.

 

그리고 두번째로 주의해야할 점은, 퍼트리는데 드는시간에 들지는 않지만, 비활성간을 활성화시키고 넘어가기 위해선 시간이 누적되는 것이다.

 

예를 들어 

 

활성 비활성 비활성 빈칸

 

이렇게 되어있을시, 

1초 뒤

활성 활성 비활성 빈칸

2초뒤

활성 활성 활성 빈칸

3초뒤

활성 활성 활성 활성

 

이렇게 3초가 걸리는 걸 알 수 있다. 비활성 바이러스는 이미 존재하던 바이러스이기 때문에 새로 퍼트린 바이러스 시간에는 포함되지 않지만, 이동통로로서는 역할을 하기 위해 시간은 지나가줘야한다.

 

인제 코드로 돌아가서 기본적인 원리는 연구소 문제들과 동일하다.

전체에 바이러스가 퍼트릴수 있는 최소시간을 구하는 것이고, 구하기 전에 전처리 과정을 해준다.

먼저 벽인 부분은 따로 wall_list로 저장해두고, 전체 바이러스가 생길수 있는 공간 N*N에서 1씩 빼준다.

왜냐하면 벽에는 바이러스가 못살기 때문이다.

또한 virus가 존재하는 경우엔, virus_list라는 set에 저장해두었다.

만약 바이러스가 생길수 있는 공간에서 입력된 바이러스의 값을 뺐을때 0이면, 이미 전부 퍼진거니 0을 출력해주면 된다.

그렇지 않을 경우, 바이러스를 퍼트리는 과정을 해준다. 앞에서 virus_list에서 M개의 combination을 뽑아낸다.

퍼지는 시간이 들어갈 주어진 공간과 같은 크기의 행렬을 만들어준다. 또한, 기본값은 -1로 시간상 존재할수 없는 값으로 초기화 해준다.

 

파이썬의 집합의 특징을 이용해 전체 virus_list에서 active_list(활성화된 바이러스)를 빼주어서, 비활성된 바이러스의 집합을 따로 만들어준다.

 

그리고 우리가 만든 spend_time이라는 행렬에 활성화된 바이러스의 위치에 0으로 초기화 시켜주고 stack에 넣어준다.

나머지는 기본적인 bfs랑 동일하다.

여기서 주의해야할 점은 deactive_virus인 공간과 빈공간에서 차이점을 둔다.

deactive_virus는 stack에 똑같이 time을 +1 해서 추가해주는 대신 spend_time은 0으로 해준다.

하지만 빈공간일때는 spend_time에 현재시간 +1 을 넣어주고, stack에도 동일하게 넣어준다. 그리고 virus_cnt를 늘려준다.

그리고 여기서 min_time을 갱신시켜준다. bfs는 최단경로를 구하는 것이기 때문에, 가장 마지막에 stack에 들어간 값이 모두 퍼트리는데 걸리는 시간이기 때문이다.

 

또한 시간을 줄여보고자, 우리가 출력하고자하는 결과 result보다 현재 min_time이 높으면 bfs를 중단시켜주었다.

 

 

이 문제에서 여러번 시도하면서 틀렸던 점은 위의 주의점 2가지를 빠르게 파악을 못했기 때문이었다. 문제를 제대로 이해하는데, 더 열심히 해야겠다.

 

이 문제를 풀면서 틀렸습니다. 됬을때 도움이 되는 반례는

 

5 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

 

answer = 0

 

4 2

0 1 1 0

2 1 1 2

2 1 1 2

0 1 1 0

 

answer = 2

 

더 많은 반례는 www.acmicpc.net/board/view/43303 , www.acmicpc.net/board/view/59703 를 참조하면 좋겠습니다.

글 읽기 - 연구소3 92%에서 틀렸습니다 뜨시는분들

글 읽기 - ☆★ 연구소3 반례모음 ★☆