BOJ - 연구소 3 17142번 (python)

❓ 문제 - 백준 연구소 3 17142번 - python 풀이법

 

출처 

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

17142번: 연구소 3

 

 

 

📝 문제해결법

1. 이 문제는 조합 + BFS로 풀었다.

• 바이러스의 행,열의 위치를 virus 리스트로 저장하고, 조합으로 m개의 활성화 바이러스를 선택한다.
• 조합으로 해당 m개의 활성화 바이러스의 경우 BFS를 돌려서 바이러스가 전부 다 퍼져나가는 시간의 최솟값을 계속 갱신한다.
• 만약 바이러스가 전부 다 퍼져나가는 최솟값을 다 갱신했는데도 min_time이 값이 초깃값과 동일하면(바이러스가 전부 다 퍼져나가지 못하기 때문) -1을 출력하고, min_time이 초깃값과 다른 최솟값으로 값이 변경되었으면 그 값을 출력한다.

2. BFS()

• check() 함수를 통해 일단 빈공간이 있는지 확인한 후 빈공간이 없다면 바이러스가 퍼져나갈 필요가 없으므로 min_time을 0으로 최솟값을 갱신한 후 bfs를 빠져나간다.
• 조합으로 얻은 m개의 활성화 바이러스의 위치에 -2로 값을 변경(활성화)해주고 해당 위치는 방문 처리 해주고 큐에 해당 위치와 이동하는데 걸리는 시간(0)을 append 해준다.
• 4방향으로 그래프를 탐색하면서 nx, ny가 범위를 벗어나지 않고 방문처리 되지 않은 상태에서 이동한 곳이 1(벽)이 아닐 때, 해당 위치를 방문처리 해주고 q에 이동시간 (time)을 1 증가해서 append 해준다. 
• 만약 해당 곳이 빈곳이라면 바이러스가 다 퍼져나갔을 때의 시간을 구하기 위해 end_time 을 time+1과 비교해서 최대값으로 갱신한다.
• 비활성화된 바이러스에서 활성화된 경우 그냥 값의 변경(2 -> 바이러스 옮김 처리)만 해주면된다.
• 연구소의 모든 곳을 탐색한 후 check() 함수를 통해 모든 곳에 바이러스를 옮겼을 경우에만 바이러스가 다 퍼져나갔을 때 시간(end_time)과  최소시간인 min_time의 값을 비교해서 최솟값을 갱신한다.

 

💻 소스코드

from collections import deque
import copy
n, m = map(int, input().split())
graph = []
virus = []
min_time = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(n):
        if data[j] == 2:
            graph[i][j] = -1
            virus.append((i, j))

def check(g):
    for i in range(n):
        for j in range(n):
            if g[i][j] == 0:
                return False
    return True


def combination(lst, num):
    result = []
    if num > len(lst):
        return result
    if num == 1:
        for l in lst:
            result.append([l])
    elif num > 1:
        for i in range(len(lst)-num+1):
            for temp in combination(lst[i+1:], num-1):
                result.append(temp+[lst[i]])
    return result

def bfs(g, combi):
    global min_time
    visited = [[False]*n for _ in range(n)]
    q = deque()
    if check(g):
        min_time = min(min_time, 0)
        return

    for c in combi:
        a, b = c
        visited[a][b] = True
        g[a][b] = -2
        q.append((a, b, 0))
    end_time = 0
    while q:
        x, y, time = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if g[nx][ny] == 1:
                    continue
                else:
                    if g[nx][ny] == 0:
                        end_time = max(end_time, time + 1)
                    g[nx][ny] = -2
                    visited[nx][ny] = True
                    q.append((nx, ny, time+1))

    if check(g):
        min_time = min(min_time, end_time)

g = copy.deepcopy(graph)
for combi in combination(virus, m):
    g = copy.deepcopy(g)
    bfs(g, combi)
    g = graph

if min_time == int(1e9):
    print(-1)
else:
    print(min_time)