연구소3

from itertools import combinations
from collections import deque

N, M = map(int, input().split())
original = [[] for _ in range(N)]
graph = [[] for _ in range(N)]
cand = []
count = 0
for i in range(N):
    original[i] = list(map(int, input().split()))
    for idx, item in enumerate(original[i]):
        if item == 2: # 활성 바이러스 후보
            cand.append([i, idx])
        if item == 0:
            count += 1

# 배열 초기화
def init():
    global original, graph
    for k in range(N):
        graph[k] = original[k].copy()

init()
size = len(cand)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(items):
    global graph
    q = deque()
    visited = [[False for _ in range(N)] for _ in range(N)]
    maxTime, tempCnt = 0, 0
    for it in items:
        r, c = it
        visited[r][c] = True
        tmp = [r, c, 0]
        q.append(tmp)
    for itt in cand:
        if itt not in items:
            graph[itt[0]][itt[1]] = "*"

    while q:
        curRow, curCol, time = q.popleft()
        maxTime = max(maxTime, time)

        for dxx, dyy in zip(dx, dy):
            if tempCnt == count:
                break
            nxtRow, nxtCol = curRow+dxx, curCol+dyy
            if nxtRow < 0 or nxtRow > N-1 or nxtCol < 0 or nxtCol > N-1:
                continue
            # 방문X + 빈칸인 경우 진행
            if not visited[nxtRow][nxtCol] and (graph[nxtRow][nxtCol] == 0 or (graph[nxtRow][nxtCol] == "*")):
                if graph[nxtRow][nxtCol] == 0:
                    tempCnt += 1
                visited[nxtRow][nxtCol] = True
                graph[nxtRow][nxtCol] = time+1
                q.append([nxtRow, nxtCol, time+1])

    # 모두 퍼뜨렸으면 성공
    if tempCnt == count:
        return maxTime
    else: # 실패
        return -1


# 가능한 조합 내림차순으로 시작
# BFS 탐색
init()
printAnswer = 987654321
res = combinations(cand, M)
for items in res:
    init()
    answer = bfs(items)
    if answer != -1: # 성공
        printAnswer = min(printAnswer, answer)

if printAnswer == 987654321:
    print(-1)
else:
    print(printAnswer)

G3

10달 전에 이 문제를 풀어봤던 기억이 난다. 그 때는 풀지 못했는데 오늘은 시간, 정확성 면에서 깔끔하게 풀어냈다.
그 기간 동안 알고리즘 면에서 실력이 늘었다고 느껴진 부분이었다.

처음에 문제를 봤을 때 N과 M의 크기가 작음(N=50, M=10) 에도 불구하고 시간 제한이 0.25초로 매우 타이트해 조합을 돌려 bfs를 돌리는 과정이 부담스럽지 않을까 걱정했었다.

하지만 결국 방법은 그것밖에 없어 보였고 우선 구현을 해보았다.

구현 로직은 일반적인 bfs 구현과 다를 것 없었다.
다만, 활성, 비활성 바이러스 칸에 대한 신경을 조금 쓰면서 표기해줘야 했다.

예를 들어, 비활성 바이러스는 방문하지 않아도 모두 감염시켰다는 조건이 만족될 수 있다.
또한, 비활성 바이러스는 지나갈 수 있는 칸이지, 지나가야만 하는 칸이 아니다.

이런 점들만 조심해서 구현해준다면 그렇게 어려운 문제는 아니었다고 생각한다.

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