[BOJ]17142 연구소3

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

로그인

풀이

연구소 시리즈는 유서가 깊다. 삼성기출 문제로 연구소, 연구소2도 만만치 않은 상대였다. 이번에는 잔뜩 긴장하고 들어갔는데, 처음에는 너무 쉽다고 느낄만큼 간단해보였다. 비활성화/활성화 바이러스가 차이가 없다고 생각했지만, 구현하고 보니 활성화 바이러스가 연구소 내를 덮는게 아니라 바이러스가 덮기만 하면 됬다. 그래서 비활성화 바이러스를 어떻게 처리해줄지가 관건이었는데, 찾아본 결과 일단 비활성화 바이러스를 벽이 아닌 공백으로 생각하고 푼 다음, 마지막에 퍼지는데 걸리는 시간을 계산할 때 비활성화 바이러스만 배제하면 되는 것이었다. 주의해야할 점은 시간제한이 굉장히 빡빡한 문제라, 혹여나 in이나 deepcopy를 사용하게 되면 여지없이 시간초과가 날 것이다. 방법만 알면 구현은 어렵지 않다, 모든 경우의 수(바이러스 중 m개를 활성화하는 경우)에 대하여 bfs를 해주고, 걸리는 시간을 저장하는 매트릭스에서 가장 큰 시간(여기서 비활성화 바이러스를 제외하고 탐색한다)을 가장 작은 시간이랑 비교하고, 만약 방문하지 못한 요소(벽이 아닌 경우)를 제외하고 모든 경우의 수를 탐색하고 정답을 출력하면 된다.

import sys
from collections import deque
from itertools import combinations
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())
institution = [list(map(int, input().split()))for _ in range(n)]
keneng = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 1e9
for i in range(n):
    for j in range(n):
        if institution[i][j] == 2:
            keneng.append([i, j])
poss = list(combinations(keneng, m))
#print(poss)
for pos in poss:
    q = deque()
    visited = [[False for _ in range(n)]for _ in range(n)]
    tempt_mtr = [[-1 for _ in range(n)]for _ in range(n)]
    for p in pos:
        q.append(p)
        tempt_mtr[p[0]][p[1]] = 0
        visited[p[0]][p[1]] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >=n or ny >= n:
                continue
            if visited[nx][ny]:
                continue
            if institution[nx][ny] != 1:
                tempt_mtr[nx][ny] = tempt_mtr[x][y] + 1
                q.append([nx, ny])
                visited[nx][ny] = True
    t = 0
    # for i in range(n):
    #     for j in range(n):
    #         print(tempt_mtr[i][j], end = ' ')
    #     print()
    # print()
    flag = False
    for i in range(n):
        for j in range(n):
            if institution[i][j] != 1:
                if tempt_mtr[i][j] == -1:
                    flag = True
                    break
                if institution[i][j] == 2:
                    continue
                if t < tempt_mtr[i][j]:
                    t = tempt_mtr[i][j]
        if flag:
            break
    if not flag:
        if answer > t:
            answer = t
print(answer) if answer != 1e9 else print(-1)