백준: 17141 연구소 2

연구소 시리즈

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

 

문제

17141번: 연구소 2

 

문제 풀이

 연구소에 바이러스 설치 가능한 위치가 있고, 설치 가능한 바이러스 수가 M개다. 바이러스는 하루마다 상, 하, 좌, 우로 바이러스를 전파시킨다. 이때 어떤 위치에서 바이러스 M개를 설치하여, 최소 날짜로 바이러스를 모두 전파시킬 수 있는 지를 찾아 반환하면 된다. 연구실 내에 벽을 제외한 모든 구간에 바이러스 전파가 불가능한 경우 -1을 반환한다.

 

 앞서 다룬 연구소에서는 DFS를 사용하여 직접 조합을 구하였지만, itertools를 사용하여 문제를 풀었다. (단, 삼성 역량테스트에서는 itertools를 사용할 수 없다.) 문제를 풀기 위해서는 다음과 같은 로직을 통해 풀 수 있다.

 

• DFS 또는 itertools를 활용하여, 바이러스 M개가 설치될 수 있는 경우의 수를 찾는다.
• 각 경우의 수마다, BFS를 호출하여 감염시킨 수는 (0의 개수 + 바이러스 수 - M)과 같으면 모두 감염된 것이다.
  • 감염시키는데 걸리는 값들 중 최솟값을 찾는다.
• 모든 경우에서 (0의 개수 + 바이러스 수 - M)와 같지 않으면 -1을 반환한다.

 

코드

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
                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:
                # 큐에서 time 정보를 활용하기 위해 0을 추가함.
                loc.append([i, j, 0])
                virus += 1
            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, virus, answer = 0, 0, inf
    
    for candi in find_loc():
        answer = min(answer, bfs(zero + virus - m, candi))
    print(answer if answer != inf else -1)