[백준 17141] 연구소 2 (python)

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

17141번: 연구소 2

연구소 2 문제

연구소에 지정된 위치에 지정된 갯수 만큼 바이러스를 심을 때 걸리는 최소 시간을 찾는 문제

 

# 사용 알고리즘

백트래킹 (완전 탐색)

너비 우선 탐색

📌문제 접근 포인트

1. 바이러스를 2인 지점을 선택하여 퍼뜨려야 한다. 이를 위해서 우선 2인 지점을 찾아주자. 나는 백트래킹을 활용한 완전 탐색을 이용했고, 임의로 체크하기 위해 3으로 바꾸어주었지만, 조합을 사용하여 따로 2인 위치만 모아 M개만큼 뽑는 식으로도 풀이 할 수 있다.

2. 백트래킹(혹은 조합)을 이용하여 지점 M개를 골랐다면, 이동 최소 거리를 찾아야하므로 BFS 탐색을 진행해주자. 큐에 선택한 M개의 지점을 전부 넣고, 방문 처리를 활용하여 탐색을 진행하여 주자. 따로 다시 최대값을 찾을 필요 없이 최대 값을 바로 갱신할 수 있도록 변수를 지정해주었다.

3. 방문 처리 비교 시에 주의해야 할 점이, 0인 지점만 탐색하는 것이 아닌, 숫자 2인 지점도 탐색을 진행해야 하므로 1이 아닐 경우 탐색하도록 만들어주자. 

4. 위처럼 구성하였다면, 2번에서 만든 변수 중에서 최소 값을 찾아서 저장 후 출력하자. 이때, 전부 탐색이 불가능 할 경우 -1로 출력이 되게 구성하면 끝.

⚙ 내가 푼 정답 코드

def implant(n, m):
    global result
    if m == M: # M개를 뽑아서
        time = spread() # 그때 시간 중에
        result = min(result, time) # 최소 저장
        return

    else :
        for i in range(n, N*N):
            r, c = i//N, i%N
            if lab[r][c] == 2:
                lab[r][c] = 3
                implant(i, m+1)
                lab[r][c] = 2

def spread():
    visited = [[0]*N for _ in range(N)]
    queue = deque()
    time = 0

    for i in range(N):
        for j in range(N):
            if lab[i][j] == 3: # 바이러스 심을 위치에
                visited[i][j] = 1 # 방문 처리후
                queue.append([i,j]) # 심자

    while queue:
        y, x = queue.popleft()
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and lab[ny][nx] != 1:
                visited[ny][nx] = visited[y][x] + 1 # 퍼뜨려보고
                queue.append([ny,nx])
                time = max(time, visited[ny][nx]) -1 #그 때 최대값

    for i in range(N):
        for j in range(N):
            if not visited[i][j] and lab[i][j] != 1: # 방문 안한 곳이 벽도 아니라면
                return float('inf') # 무한대 반환(나중에 최소 값 비교를 위함)
    return time

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
lab = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
move = [[0,1],[0,-1],[1,0],[-1,0]]
result = float('inf')
implant(0,0)
if result == float('inf'):
    result = -1
print(result)