[백준 - Python] 17142 - 연구소 3

0. 문제 링크

 

 

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

17142번: 연구소 3

---

1. 풀이 방법

 

 

2023.02.21 - [Computer Science/알고리즘] - [백준 - Python] 17141 - 연구소 2

공간을 다시 정의했다. 어차피 활성 바이러스 된다해도, 기존에 BFS에서 돌던게 있으니까 상관 없고, 결과적으로 진짜 비어있는 공간만 채우면 된다.

그래서 해당 글의 코드를 그대로 가져와서 그냥 공간만 다시 정의하고 제출했더니 성공;

---

2. 코드

 

 

import sys
import itertools
from collections import deque
from copy import deepcopy


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


def bfs(board, it, n, empty):
    dq = deque(it)
    for y, x in it:
        board[y][x] = 1
    cnt = 1
    empty_cnt = 0
    while dq:
        for _ in range(len(dq)):
            y, x = dq.popleft()
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                if 0 <= ny < n and 0 <= nx < n:
                    if board[ny][nx] == 0:
                        board[ny][nx] = float('inf')
                        dq.append([ny, nx])
                        empty_cnt += 1
                    if board[ny][nx] == 2:
                        board[ny][nx] = float('inf')
                        dq.append([ny, nx])
        if empty_cnt == empty:      # 만약 모든 공간이 채워진다면 그대로 cnt를 반환함
            return cnt
        cnt += 1         # cnt는 모든 바이러스가 한 칸씩 번졌을 때, 1씩 증가함
    else:
        return 9999       # 만약 바이러스가 모두 퍼지지 않았을 때는 9999를 반환함


def sol():
    n, m = map(int, sys.stdin.readline().split())
    board = [[b for b in map(int, sys.stdin.readline().split())] for _ in range(n)]
    board_ori = deepcopy(board)
    empty = 0
    pos = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == 2:
                pos.append([i, j])
            elif board[i][j] == 0:
                empty += 1
    if empty == 0:      # 채워야 하는 공간의 개수가 0이라면 0초가 걸림
        print(0)
        exit(0)
    minimum = float('inf')
    for it in itertools.combinations(pos, m):       # 모든 조합을 짜서 바이러스를 넣어봄
        temp = bfs(board, it, n, empty)
        minimum = temp if temp < minimum else minimum       # 바이러스를 모두 퍼뜨릴 수 있는 최소 시간
        board = deepcopy(board_ori)
    print(minimum if minimum != 9999 else -1)       # 9999는 바이러스를 모두 퍼뜨릴 수 없는 경우이므로 -1을 출력함


sol()

---

3. 마무리

 

 

날먹해서 기분이 좋다.