[백준] 17142번 - 연구소 3 (파이썬)

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

# 연구소 3
import sys
import copy
from collections import deque
input = sys.stdin.readline
MAX = sys.maxsize
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
result = MAX


def bfs(arr):
    global result
    time = [[0] * N for _ in range(N)]
    q = deque()
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 'a':
                q.append((i, j))
                time[i][j] = 1
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                if time[nx][ny] == 0:
                    if arr[nx][ny] == 0 or arr[nx][ny] == 2:
                        time[nx][ny] = time[x][y] + 1
                        q.append((nx, ny))
                    else:
                        time[nx][ny] = -1
    find_min_time(arr, time)


def find_min_time(arr, time):
    global result
    temp = -1
    for i in range(N):
        for j in range(N):
            if time[i][j] == 0:
                if arr[i][j] == 0:
                    return
            elif time[i][j] != -1 and arr[i][j] != 2 and arr[i][j] != 'a':
                temp = max(temp, time[i][j])
    if result > temp - 1:
        result = min(result, temp-1)


def active_virus(arr, count, temp):
    if count == virus_num:
        bfs(arr)
        return
    for start in range(temp+1, len(virus), 1):
        x, y = virus[start]
        arr[x][y] = 'a'
        active_virus(arr, count+1, start)
        arr[x][y] = 2


N, virus_num = map(int, input().split())
arr = []
virus = []
zerocount = 0
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 2:
            virus.append((i, j))
        if arr[i][j] == 0:
            zerocount += 1

temp = copy.deepcopy(arr)
active_virus(temp, 0, -1)

if zerocount == 0:
    print(0)
else:
    if result == MAX:
        print(-1)
    else:
        print(result)

 

BFS, 백트랙킹

1. 백트랙킹으로 바이러스를 해당개수(virus_num)만큼 고르기(active_virus)

  - bfs를 실행하여 q가 빌 때까지 time리스트에 바이러스가 퍼지는데 걸린 시간 초기화

  - result와 time리스트 내부에서 가장 큰값(바이러스가 있는 위치 제외), 둘 중 작은 값을 result로 초기화(find_min_time)

2. 1번을 모든 경우의 수 만큼 반복

3. result 출력 (초기 리스트에 0이 없으면, 0출력)

 

의식의 흐름대로 막 풀었기에 코드가 매우 지저분하다...

백트랙킹 말고 콤비네이션을 이용하면 더 쉽게 할 수 있다.