[백준] 17142 연구소 python

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

17142번: 연구소 3

삼성 기출 문제이다. 이전에 풀었던 연구소 문제를 풀었는데 그 문제는 벽을 생성해서 안전구역을 최대화 시키는 것이었다. 

이번 연구소 문제는 바이러스를 M개 활성화 시켜서 전체 구역을 감염시키는 최소 시간을 구하면 된다.

 

이 문제를 풀기 위해 다음과 같은 순서로 구현했다.

1) 입력을 받을 때 지도(이차원배열, _map)을 생성하고, 바이러스의 모든 위치를 파악한다(viruses).

2) 모든 바이러스에서 원소의 개수가 M개인 조합을 만들고, 이를 사용해 최소 시간을 파악한다.

2-1) 바이러스 M개를 큐에 넣고 BFS를 진행한다. 이때 범위 내에 있고 방문하지 않았으며 벽이 아니면 큐에 넣는 방식으로 진행한다.

2-2) BFS가 끝나면 지도에서 빈 칸인 부분(_map[i][j] == 0)들만 확인해서 가장 큰 값을 리턴한다. 만약 visit[[i][j]가 0인 값이 있으면 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우이므로 INF 값을 리턴한다. 

2-3) 모든 바이러스 조합에 대해서 2-1), 2-2)를 반복한다.

3) 최소 시간을 출력한다. 모든 조합을 돌려도 INF 값이 남아있으면 바이러스를 어떻게 놓아도 바이러스를 퍼트릴수 없으므로 -1을 출력한다.

 

 

import sys; input = sys.stdin.readline
from collections import deque
from itertools import combinations

INF = 1234567890
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def bfs(start_indexes):
    global N, M, _map, viruses
    visit = [[0 for _ in range(N)] for _ in range(N)]
    q = deque()
    for idx in start_indexes:
        q.append([0, *viruses[idx]])
    while q:
        dist, r, c = q.popleft()
        if visit[r][c]:
            continue
        visit[r][c] = dist
        for dr, dc in d:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N \
                    and not visit[nr][nc]:
                if _map[nr][nc] != 1:  # empty space
                    q.append([dist + 1, nr, nc])


    # check empty space and find max value
    ret = 0
    for i in range(N):
        for j in range(N):
            if _map[i][j]: continue
            if not visit[i][j]:
                return INF
            ret = max(ret, visit[i][j])
    return ret


def main():
    global N, M, _map, viruses
    # 0 input
    N, M = map(int, input().split())
    _map = []
    viruses = []
    for i in range(N):
        _map.append(list(map(int, input().split())))
        for j in range(N):
            if _map[i][j] == 2:
                viruses.append([i, j])

    # 1 bfs for combination with M viruses
    answer = INF
    for indexes in combinations(range(len(viruses)), M):
        answer = min(answer, bfs(indexes))

    # 2 output, print answer
    if answer == INF:
        print(-1)
    else:
        print(answer)


if __name__ == "__main__":
    main()

 

그렇게 어려운 문제는 아니었지만 문제를 제대로 읽어야 풀수있는 문제였다.