[백준 17142] 연구소 3

백준 17142

🔍 알고리즘 분류

• 브루트포스
• DFS
• 백트래킹
• BFS

💡 문제 풀이

1. 바이러스 조합 생성: combinations 또는 DFS 이용
2. 조합 생성 완료 시 BFS 진행
   1) q에 바이러스 위치 모두 추가
   2) 바이러스 방문 여부 visited, 퍼뜨리는 시간 max_time, 빈칸 갯수 empty_cells, 바이러스 퍼진 칸 filled 초기화
   3) 상하좌우가 0 또는 2 일 때 퍼뜨리기
   • 빈칸 0 일 때: 걸린 최대시간 갱신, filled 증가
   • 방문 처리, q에 다음 위치 추가
3. 빈칸 모두 채운 경우에만 모두 채우는 데 걸린 최솟값(=답) 갱신

📄 코드

• Python

import sys
from collections import deque
input = sys.stdin.readline

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

# 연구소 초기화
for i in range(n):
    row = list(map(int, input().split()))
    arr.append(row)
    for j in range(n): # 바이러스 위치 저장
        if row[j] == 2:
            virus.append((i, j))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans = int(1e9)

def dfs(idx, cnt, combi):
    global ans
    # 조합한 바이러스 수가 m개일 때 바이러스 퍼뜨리기
    if cnt == m:
        visited = [[int(1e9)] * n for _ in range(n)] # 바이러스 방문 여부
        max_time = 0 # 모든 칸에 바이러스를 퍼뜨리는 시간
        empty_cells = sum(row.count(0) for row in arr) # 빈칸 갯수
        filled = 0 # 바이러스가 퍼진 칸
        q = deque()

        # 큐에 활성 바이러스 추가
        for x, y in combi:
            visited[x][y] = 0
            q.append((x, y))

        # 바이러스 퍼뜨리기
        while q:
            x, y = q.popleft()
            for dir in range(4):
                nx = x + dx[dir]
                ny = y + dy[dir]
                if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] > visited[x][y] + 1:
                    if arr[nx][ny] == 0: # 빈칸
                        visited[nx][ny] = visited[x][y] + 1
                        max_time = max(max_time, visited[nx][ny])
                        filled += 1
                        q.append((nx, ny))
                        
                    elif arr[nx][ny] == 2: # 비활성 바이러스
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))

        # 빈칸 모두 채운 경우에만
        if filled == empty_cells:
            ans = min(ans, max_time)
            return max_time
        
        return int(1e9)
    
    # 바이러스 조합 생성
    for i in range(idx, len(virus)):
        combi.append(virus[i])
        dfs(i + 1, cnt + 1, combi)
        combi.pop()

dfs(0, 0, [])

# 정답 출력
print(ans if ans != int(1e9) else -1)