[BOJ] 17141 연구소2 파이썬

1. 문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

2. 입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

3. 출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

 

 

연구소 1과 같은 방법만 안다면 간단한 문제이다.

그냥 모든 바이러스의 경우의 수를 완전탐색해주면된다.

하지만 여기엔 생각하지 못한 히든테케가 있었으니..

      

      

      

    
    

      <python />
    
5 2
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 2 2 1

위 테케는 답이 0인데 -1을 출력해서 98%에서 틀리고있었다...

 

조건문추가해서 정답처리 완료~

 

      

      

      

    
    

      <python />
    
import sys
import copy
from collections import deque
from itertools import combinations
sys.stdin.readline

n, m = map(int, input().rstrip().split(" "))

board = []
virus_pos = []
zero_count = 0
for i in range(n):
    temp = list(map(int, input().rstrip().split(" ")))
    for j in range(n):
        if(temp[j] == 2):
            virus_pos.append((i, j))
            temp[j] = 0  # 바이러스 있는곳도 랜덤으로 위치시켜줄거니까 일단 0
            zero_count += 1  # 빈공간 몇개인지 세주기
        elif(temp[j] == 0):
            zero_count += 1  # 빈공간 몇개인지 세주기
    board.append(temp)


def bfs(n, board, virus_lists, zero_count):
    # 상,하,좌,우
    direction = [
        (-1, 0), (1, 0), (0, -1), (0, 1)
    ]

    newBoard = copy.deepcopy(board)
    visited = [[-1]*n for _ in range(n)]
    q = deque()
    count = 0
    for v in virus_lists:  # 바이러스 먼저 큐에 넣고, 방문처리
        q.append(v)
        visited[v[0]][v[1]] = count

    max_time = 0
    available_space = zero_count - len(virus_lists)  # 현재 남은 빈공간개수

    while(len(q) != 0):
        x, y = q.popleft()

        for i in range(4):
            new_x, new_y = x+direction[i][0], y+direction[i][1]

            if(new_x >= 0 and new_y >= 0 and new_x < n and new_y < n):
                if(newBoard[new_x][new_y] == 0 and visited[new_x][new_y] == -1):
                    q.append((new_x, new_y))
                    visited[new_x][new_y] = visited[x][y]+1  # 카운트
                    max_time = max(max_time, visited[new_x][new_y])
                    available_space -= 1  # 빈공간 1개 삭제

                    if(available_space <= 0):  # 빈공간이 0이 되었으면
                        # print()
                        # for v in visited:
                        #     print(v)
                        return max_time
    # print()
    # for v in visited:
    #     print(v)
    # print(available_space)
    if(available_space <= 0):
        '''
        예제 히든테케 통과용
        5 2
        1 1 1 1 1
        1 1 1 1 1
        1 1 1 1 1
        1 1 1 1 1
        1 1 2 2 1
        '''
        return max_time

    return -1  # 빈공간0에 도달하지 못했음


answer = float('inf')
for s in combinations(virus_pos, m):
    res = bfs(n, board, s, zero_count)
    if(res != -1):
        answer = min(answer, res)

if(answer == float("inf")):  # 전부 -1이었던것..
    print(-1)
else:
    print(answer)

 

 

한번 누르면 2시간동안 보이지 않아요 ㅎㅎ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

원치 않을 경우 를 눌러주세요