[백준/파이썬] 17141. 연구소2

[Gold IV] 연구소 2 - 17141

문제 링크

성능 요약

메모리: 114932 KB, 시간: 196 ms

분류

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 격자 그래프

제출 일자

2025년 10월 1일 16:19:16

문제 설명

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 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

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

입력

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

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

출력

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

 

from collections import deque

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

INF = 1<<32
def combine(arr, k) :
    visited = [False for _ in range(len(arr))]
    res = []
    combinations(0, k, arr, visited, [], 0, res)

    return res

def combinations(bgn, end, nums, visited, buildings: list, depth, res) :
    if depth == end :
        res.append(buildings[:])
        return

    for idx in range(bgn, len(nums)) :
        if visited[idx] :
            continue

        visited[idx] = True
        combinations(idx+1, end, nums, visited, buildings + [nums[idx]], depth + 1, res)
        visited[idx] = False

def bfs(virus, arr, empty) :
    N = len(arr)
    q = deque(virus)
    time = 0

    visited = [[INF for _ in range(N)] for _ in range(N)]
    for vi, vj in virus :
        visited[vi][vj] = 0

    while q :
        ci, cj = q.popleft()

        if arr[ci][cj] == 0 :
            empty -= 1

        if not empty :
            break

        for d in range(4) :
            ni, nj = ci + di[d], cj + dj[d]
            if 0 <= ni < N and 0 <= nj < N and arr[ni][nj] != 1 :
                if visited[ni][nj] > visited[ci][cj] + 1 :
                    q.append((ni, nj))
                    visited[ni][nj] = visited[ci][cj] + 1
                    time = visited[ni][nj]

    if not empty :
        return time
    else :
        return INF

def main() :
    """
    0: 빈칸, 1: 벽, 2: 바이러스 놓을 수 있는 칸

    """
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    tbl = []
    empty = 0
    for i in range(N) :
        for j in range(N) :
            if arr[i][j] == 2 :
                tbl.append((i, j))
                arr[i][j] = 0
            if arr[i][j] != 1 :
                empty += 1
    res = INF
    tbl_virus = combine(tbl, M)
    for virus in tbl_virus :
        res = min(res, bfs(virus, arr, empty))

    if res == INF :
        print(-1)
    else :
        print(res)

if __name__ == "__main__" :
    main()

접근할 때 어려움이 있었다. 

Main함수

• tbl : 시작점을 모두 받아 넣을 배열. 이후 조합 함수에 넣어 len(tbl) combination M개 만큼의 조합을 구한다.
• empty : 바이러스가 퍼져 나갈 수 있는 공백의 갯수를 세기 위한 변수
• res : 정답 변수. 최소값을 구할것이기 때문에 초기값으로 아주 큰 수로 설정. 
• tbl_virus : 위의 tbl을 조합 함수에 넣어 조합을 구한다.

combine - combinations 함수

• 이 변수들은 앞서 Leetcode 의 Permutations 문제에서 배웠던 조합과 순열을 하나의 구조로 공부한 후 변수만 달리 하면 한가지를 공부하고도 두 가지를 모두 사용할 수 있는 방법이다. 
• 백트래킹을 활용한 구조이므로 같이 공부해도 좋을 듯 하다.
• 순열과의 차이점 : combinations 재귀로 들어가는 코드에서 bgn 을 0으로 두냐, idx + 1 로 두냐의 차이일 것이다. 또한 end 에서 순열은 len(nums)를 받아오나, 조합은 k를 받아와야 하기 때문에 여기에서도 차이점이 발생한다. 이 부분에 대해서는 이후 스터디에서 자세하게 물어봐야 좋을 것 같다. 배웠는데 까먹음...

BFS함수

• 구한 조합 배열을 deque로 변환함. viurs:List -> deque
• 이후로는 일반적인 BFS 같지만 정답처리를 조금 다르게 해주었다. 
  • 현재 위치가 0이면, emtpy를 -1 해주고 남아있는 empty를 계산한다. 
  • empty 가 0이면 정답처리 -> BFS를 정상적으로 마쳤다면 time을, 모두 마치지 못하고 종료되었다면 INF 값을 반환
  • 다음 방향으로 나아가기 위해 4가지 조건을 탐색 (네 방향, 범위 내, 미방문, 조건: 다음 방문이 벽이 아니라면)
  • 마지막 정답 처리.

이 문제를 보자마자 들었던 생각

• arr[i][j] == 2 인 좌표 (i, j) 를 따로 저장해놓는다. 그리고 해당 지역을 교체
• 조합을 사용하자. => 조합 함수 짜기
• BFS 를 수행하자 => BFS 함수 짜기
• 정답처리를 어떻게 할 것인가. 최소값을 구하는 거니까 아주 큰 수를 기본상태로 둬서 최소값으로 줄여가자. 

정답 처리가 좀 미흡했는데 이런 부분을 조금 더 다듬어 가야겠다.