[백준] 파이썬 _ 연구소3

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

17142번: 연구소 3

눙물,,,

 

문제유형: BFS,그래프탐색,

 

 

문제풀이 :

 

• 비활성 바이러스에 활성바이러스가 닿으면 비활성도 활성이 된다..... 는 것을 문제에서 놓침. 또 이때에는 시간이 증가하지 않음 그냥 변하기만함..
• 활성바이러스가 빈칸으로 복제될때만 시간이 증가하는것이고 바이러스에 닿으면 그냥 변하게만 한다.

 

• 가능한 m개의 바이러스 조합에 대해 bfs를 돌려야되는데 이때 graph를 deepcopy하면 시간초과가난다. graph는 그대로두고 map배열을 이용했다.

 

정답코드 : 

import sys

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def solution(map, virus, empty, visited):
    n = len(map)
    time = 0
    count = 0

    for v in virus:
        map[v[0]][v[1]] = 0
        visited[v[0]][v[1]] = True

    while virus:
        curr = virus.popleft()
        # v의 인접한 위치를 감염시킨다.
        x, y = curr[0], curr[1]
        for i in range(4):
            # 이동가능하면서 빈칸이면
            if 0 <= x + dx[i] < n and 0 <= y + dy[i] < n and not visited[x + dx[i]][y + dy[i]]:
                # 벽이 아니면
                if graph[x + dx[i]][y + dy[i]] != 1:
                    map[x + dx[i]][y + dy[i]] = map[x][y] + 1
                    # 해당좌표를 큐에 넣는다.
                    virus.append((x + dx[i], y + dy[i]))
                    if graph[x + dx[i]][y + dy[i]] == 0:
                        count += 1
                        time = map[x][y] + 1
                    visited[x + dx[i]][y + dy[i]] = True

                if empty == count:
                    break

    if count < empty:
        return -1
        # 최소시간을 리턴한다.
    return time


# 전체 바이러스중에서 m개의 바이러스를 활성화로 변경하여
# 모든 빈칸을 감염으로 만든다.
# 위 과정을 최소시간으로 하는 최소시간을 출력

# 1. 바이러스중에서 고를수있는 m개를 고른다.
# 2. m개의 위치에서 동시에 바이러스를 퍼져나가게 한다.
from collections import deque
from itertools import combinations

n, m = map(int, input().split())
graph = []

empty = 0

virus_all = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 2:
            virus_all.append((i, j))
        elif temp[j] == 0:
            empty += 1
    graph.append(temp)

import copy

answer = 2501
# virus를 m개 뽑아서 해당좌표를 0으로 만든뒤에 solution에 전달
for case in combinations(virus_all, m):
    virus = deque()
    visited = [[False] * n for _ in range(n)]
    map = [[-1] * n for _ in range(n)]
    for c in case:
        virus.append(c)

    s = solution(map, virus, empty, visited)

    if s == -1:
        continue
    answer = min(answer, s)

if answer == 2501:
    print(-1)
else:
    print(answer)