백준: 17142 연구소 3

연구소 시리즈

• 연구소
• 연구소 2
• 연구소 3

 

문제

17142번: 연구소 3

 

문제 풀이

 앞서 다룬 연구소 2 문제에서 조건이 조금 달라진 문제이다. 연구소 2에서는 바이러스를 설치하고, 바이러스가 설치가능한 위치이지만 설치되어있지 않을 경우 해당 영역에도 바이러스가 전파 가능하다. 하지만 이 문제에서는 바이러스가 설치 가능한 위치에 모두 설치되어 있고, `활성화`, `비활성화` 상태로 나뉘게 된다. 따라서 이미 바이러스가 설치된 곳이므로 전파가 불가능하여 `바이러스가 있는 위치를 제외시켜야 한다는 차이점`이 있다. 또한, `바이러스를 전파하여야 하는 수는 0의 개수와 같아진다는 차이점`도 있다.

 

코드

from sys import stdin
from collections import deque
from itertools import combinations
from math import inf


def visitable(x, y, visited):
    return 0 <= x < n and 0 <= y < n and graph[x][y] != 1 and not visited[x][y]


def bfs(infect, start):
    q = deque(start)
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    visited = [[False] * n for _ in range(n)]
    cur_time, cur_infect = 0, 0

    # 초기 바이러스 활성화 지점 방문 표시.
    for x, y, _ in q:
        visited[x][y] = True

    while q:
        x, y, time = q.popleft()
        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy
            if visitable(next_x, next_y, visited):
                visited[next_x][next_y] = True
                if graph[next_x][next_y] == 0:
                    # 설치된 바이러스는 제외하기 위함.
                    cur_time = time + 1
                    cur_infect += 1
                q.append((next_x, next_y, time + 1))

    return cur_time if cur_infect == infect else answer


def find_loc():
    global zero, virus
    loc = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 2:
                loc.append([i, j, 0])
            if graph[i][j] == 0:
                zero += 1
    return combinations(loc, m)


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    zero, answer = 0, inf
    
    for candi in find_loc():
        answer = min(answer, bfs(zero, candi))
    print(answer if answer != inf else -1)