연구소3

문제 파악

주어진 N X N 보드에서 M개의 바이러스를 선택하여 퍼뜨렸을때 모든 지역이 감염되는 최소 시간을 궇는 문제이다.

17142번: 연구소 3

접근 방법

1. 바이러스를 선택할 수 있는 모든 조합을 생성한다.
2. 각 조합마다 BFS 알고리즘을 사용하여 바이러스 시뮬레이션.
3. 모든 지역이 감염되었다면 결과를 추가한다.
4. 최소 시간을 반환한다.

코드 구현

import sys
from collections import deque
from itertools import combinations

N, M = map(int, sys.stdin.readline().split())

board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 바이러스 퍼뜨리기
def virus_bfs(cords):
    answer = 0
    visited = [[False] * N for _ in range(N)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    temp = [row[:] for row in board]
    q = deque()
    for x, y in cords:
        q.append((x, y))
        visited[x][y] = True
        temp[x][y] = 0
    while q:
        cur_x, cur_y = q.popleft()
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and not visited[next_x][next_y]:
                if temp[next_x][next_y] == -4:
                    temp[next_x][next_y] = temp[cur_x][cur_y] + 1
                    # print(answer)
                    answer = max(answer, temp[next_x][next_y])
                    q.append((next_x, next_y))

                elif temp[next_x][next_y] == -2:
                    temp[next_x][next_y] = temp[cur_x][cur_y] + 1
                    q.append((next_x, next_y))

                visited[next_x][next_y] = True

    for row in temp:
        print(row)

    if is_valid(temp):
        results.append(answer)

def is_valid(board):
    for i in range(N):
        for j in range(N):
            if board[i][j] == -4:
                return False
    return True

def lab():

    find_virus()
    for cords in combinations(virus_cord, M):
        virus_bfs(cords)

    if results:
        print(min(results))
    else:
        print(-1)

# 바이러스의 위치를 찾는 함수
def find_virus():
    for x in range(N):
        for y in range(N):
            if board[x][y] == 2:  # 바이러스가 있는 위치
                virus_cord.append((x, y))
                board[x][y] = -2  # 바이러스가 있는 위치는 -2로 설정
            elif board[x][y] == 1:  # 벽이 있는 위치
                board[x][y] = -1  # 벽이 있는 위치는 -1로 설정
            else:  # 빈 공간
                board[x][y] = -4  # 빈 공간은 -4로 설정

virus_cord = []
results = []
lab()