백준: 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)