백준 연구소 3 [17142] 파이썬(Python) 코드 + 해설

백준 연구소3 17142 문제

문제 설명

인체에 치명적인 바이러스를 연구하던 연구소에 누군가 침입하여 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 처음에는 모든 바이러스가 비활성 상태이며, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되어 퍼지며, 1초가 걸린다.

우리는 연구소의 바이러스 위치 중 M개를 선택하여 활성 상태로 변경하려고 한다. 연구소는 N×N 크기의 정사각형이며, 각 칸은 빈 칸(0), 벽(1), 바이러스 위치(2)로 이루어져 있다.

활성 바이러스가 비활성 바이러스가 있는 칸으로 가면, 해당 바이러스는 활성 상태로 변한다. 모든 빈 칸에 바이러스를 퍼뜨리는 데 걸리는 최소 시간을 구하는 것이 목표이다.

문제 접근

이 문제는 다음과 같은 특징을 가진다:

• 바이러스는 동시에 퍼진다.
• 바이러스는 빈 칸과 비활성 바이러스 칸으로 퍼질 수 있다.
• 활성 바이러스가 비활성 바이러스 칸에 도달하면, 그 바이러스는 활성화되어 퍼지기 시작한다.
• 벽은 바이러스의 진행을 막는다.

문제 해결을 위해 다음과 같은 접근을 한다:

1. M개의 활성 바이러스 위치 선택: 주어진 바이러스 위치 중 M개를 선택하는 모든 조합을 고려한다.
2. 각 조합에 대해 BFS 수행: 선택된 활성 바이러스를 시작점으로 하여 BFS를 수행하여 바이러스가 퍼지는 시간을 계산한다.
3. 모든 빈 칸에 바이러스가 도달하는 최소 시간 갱신: 각 조합에서 계산된 시간을 비교하여 최소 시간을 찾는다.
4. 불가능한 경우 처리: 바이러스를 어떻게 활성화해도 모든 빈 칸에 도달할 수 없는 경우 -1을 출력한다.

알고리즘

1. 바이러스 위치 저장: 입력에서 바이러스가 있는 위치(값이 2인 칸)를 모두 저장한다.
2. 활성 바이러스 조합 생성: 바이러스 위치 리스트에서 M개를 선택하는 모든 조합을 생성한다.
3. 각 조합에 대해 BFS 수행:
   • 큐 초기화: 선택된 활성 바이러스 위치를 모두 큐에 넣고, 해당 위치를 방문 처리한다.
   • BFS 탐색: 큐에서 위치를 꺼내어 상하좌우로 퍼뜨린다.
     • 빈 칸(0) 또는 비활성 바이러스(2)인 경우 이동 가능하다.
     • 이동한 위치가 빈 칸인 경우 시간을 갱신한다.
     • 방문한 위치는 방문 처리한다.
   • 모든 빈 칸에 도달했는지 확인: BFS 종료 후, 모든 빈 칸에 바이러스가 도달했는지 확인한다.
4. 최소 시간 갱신: 모든 조합에 대해 위 과정을 반복하여 최소 시간을 갱신한다.

단계별 코드 구현

1. 입력 및 초기화

import sys
import itertools
import collections

input = sys.stdin.readline

N, M = map(int, input().split())
lab = []
virus_positions = []
empty_count = 0

for i in range(N):
    row = list(map(int, input().split()))
    lab.append(row)
    for j in range(N):
        if row[j] == 2:
            virus_positions.append((i, j))
        elif row[j] == 0:
            empty_count += 1

 

• virus_positions: 바이러스 위치를 저장하는 리스트
• empty_count: 빈 칸의 수를 저장하여 모든 빈 칸에 바이러스가 도달했는지 확인하기 위해 사용

2. 활성 바이러스 조합 생성 및 BFS 수행

def bfs(active_viruses):
    visited = [[-1]*N for _ in range(N)]
    queue = collections.deque()
    for x, y in active_viruses:
        queue.append((x, y))
        visited[x][y] = 0
    max_time = 0
    empty = empty_count
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == -1:
                    if lab[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y] + 1
                        max_time = visited[nx][ny]
                        empty -= 1
                        queue.append((nx, ny))
                    elif lab[nx][ny] == 2:
                        visited[nx][ny] = visited[x][y] + 1
                        queue.append((nx, ny))
    if empty == 0:
        return max_time
    else:
        return -1

• visited: 방문 여부와 시간을 저장하는 2차원 리스트
• max_time: 바이러스가 퍼지는 데 걸린 최대 시간
• empty: 남은 빈 칸의 수

3. 최소 시간 계산

from itertools import combinations

min_time = sys.maxsize
if empty_count == 0:
    min_time = 0
else:
    for active_combination in combinations(virus_positions, M):
        time = bfs(active_combination)
        if time != -1 and time < min_time:
            min_time = time

if min_time == sys.maxsize:
    print(-1)
else:
    print(min_time)

• 모든 활성 바이러스 조합에 대해 BFS를 수행하고, 최소 시간을 갱신한다.
• 빈 칸이 처음부터 없는 경우(min_time이 0인 경우)도 처리한다.

백준 17142 연구소 3 파이썬(Python) 정답 코드

import sys
import itertools
import collections

input = sys.stdin.readline

N, M = map(int, input().split())
lab = []
virus_positions = []
empty_count = 0

for i in range(N):
    row = list(map(int, input().split()))
    lab.append(row)
    for j in range(N):
        if row[j] == 2:
            virus_positions.append((i, j))
        elif row[j] == 0:
            empty_count += 1

def bfs(active_viruses):
    visited = [[-1]*N for _ in range(N)]
    queue = collections.deque()
    for x, y in active_viruses:
        queue.append((x, y))
        visited[x][y] = 0
    max_time = 0
    empty = empty_count
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visited[nx][ny] == -1:
                    if lab[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y] + 1
                        max_time = visited[nx][ny]
                        empty -= 1
                        queue.append((nx, ny))
                    elif lab[nx][ny] == 2:
                        visited[nx][ny] = visited[x][y] + 1
                        queue.append((nx, ny))
    if empty == 0:
        return max_time
    else:
        return -1

min_time = sys.maxsize
if empty_count == 0:
    min_time = 0
else:
    for active_combination in itertools.combinations(virus_positions, M):
        time = bfs(active_combination)
        if time != -1 and time < min_time:
            min_time = time

if min_time == sys.maxsize:
    print(-1)
else:
    print(min_time)

결론

이 문제는 조합과 BFS 탐색을 이용하여 해결할 수 있다. 바이러스의 위치 중 M개를 선택하는 모든 경우를 고려하고, 각 경우마다 BFS를 수행하여 최소 시간을 계산한다. BFS를 효율적으로 구현하고, 불필요한 계산을 줄이는 것이 중요하다.

특히, 시간 제한이 매우 빡빡하므로 입력 및 출력에서 sys.stdin.readline을 사용하고, BFS에서 방문 체크를 효율적으로 해야 한다.

 

백준 17142 제출 결과