[알고리즘] 연구소3 python(boj 17142)

 

백준 - 연구소 3 문제 풀이

문제 분석

이 문제는 N×N 크기의 연구소에서 M개의 바이러스를 활성화시켜 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제입니다. 주요 조건은 다음과 같습니다:

1. 바이러스는 활성/비활성 상태가 있음
2. 활성 바이러스는 상하좌우로 동시에 퍼짐
3. 활성 바이러스가 비활성 바이러스를 만나면 활성화됨
4. M개의 바이러스만 활성화 가능

풀이 과정

1. 초기 설정

N, M = list(map(int, input().split()))
virus = []  # 바이러스 위치 저장
board = []  # 연구소 상태 저장
targetCount = 0  # 바이러스를 퍼뜨려야 하는 빈 칸의 수

• 입력으로 받은 연구소 상태에서 바이러스의 위치를 따로 저장합니다.
• targetCount는 바이러스를 퍼뜨려야 하는 빈 칸(0)의 개수입니다.

2. 바이러스 선택과 시뮬레이션

문제 해결을 위해 두 개의 핵심 함수를 사용합니다:

1. dfs(): M개의 활성 바이러스 선택
2. next(): 선택된 바이러스들의 전파 시뮬레이션

DFS와 Next 함수의 동작 과정

DFS 함수 분석

def dfs(depth: int, virus):
    global targetCount, currentVirus, res
    if depth == M:  # M개의 바이러스를 모두 선택했을 때
        copiedBoard = copy.deepcopy(board)
        curTargetCount = targetCount
        curVirus = currentVirus[:]
        res = min(res, next(copiedBoard, curTargetCount, curVirus))
        if res == 0:
            print(0)
            exit(0)
        return

DFS 함수는 다음과 같은 순서로 동작합니다:

1. 바이러스 조합 생성
   •  depth가 M이 될 때까지 재귀적으로 바이러스를 선택
   •  currentVirus 배열에 선택된 바이러스들의 위치를 저장
2. 시뮬레이션 실행
   •  M개가 선택되면 (depth == M) 현재 상태를 복사
   •  next() 함수를 호출하여 바이러스 전파 시뮬레이션 실행
   •  최소 시간(res)을 갱신

Next 함수 분석

def next(board, targetCount, virus):
    curTime = 0
    visited = {}
    for row, col in virus:
        visited[(row, col)] = True

    while targetCount != 0 and virus:
        nextVirus = []
        for row, col in virus:
            for dir in dirs:
                nextRow, nextCol = row + dir[0], col + dir[1]
                if 0 <= nextRow < N and 0 <= nextCol < N and visited.get((nextRow, nextCol)) == None and board[nextRow][nextCol] != 1:
                    if board[nextRow][nextCol] == 0:
                        targetCount -= 1    
                    board[nextRow][nextCol] = 2
                    nextVirus.append((nextRow, nextCol))
                    visited[(nextRow, nextCol)] = True
        virus = nextVirus
        curTime += 1

Next 함수는 BFS 방식으로 바이러스 전파를 시뮬레이션합니다:

1. 초기 설정
   •  visited 딕셔너리로 방문 체크
   •  활성화된 바이러스의 위치를 방문 처리
2. 바이러스 전파 과정
   •  현재 활성 바이러스들에서 상하좌우로 전파 
   •  새로운 위치가 유효하고 방문하지 않았으며 벽이 아닌 경우 전파
   •  빈 칸을 만나면 targetCount 감소
   •  시간(curTime) 증가
3. 종료 조건
   •  모든 빈 칸에 바이러스가 퍼졌거나 (targetCount == 0)
   •  더 이상 전파할 수 없을 때 종료

값 업데이트 과정

1. DFS에서의 업데이트
   • 각 바이러스 조합마다 시뮬레이션 결과와 현재까지의 최소 시간을 비교
   • 더 작은 값으로 res 갱신
2. res = min(res, next(copiedBoard, curTargetCount, curVirus))
3. Next에서의 업데이트
   •   빈 칸이 채워질 때마다 targetCount 감소
   •   각 전파 단계마다 시간 증가
4. targetCount -= 1 # 빈 칸을 채울 때마다 갱신 curTime += 1 # 전파 단계마다 시간 증가
5. 최종 결과
   • 모든 조합을 시도한 후 res 값 출력
   • res가 sys.maxsize이면 모든 칸에 바이러스를 퍼뜨릴 수 없는 경우이므로 -1 출력

이러한 과정을 통해 문제에서 요구하는 최소 시간을 효율적으로 계산할 수 있습니다.

 

 

전체코드

 

import sys
import functools
import copy
input = sys.stdin.readline

N, M = list(map(int, input().split()))

virus = []
board = []
targetCount = 0
for row in range(N) :
    cur = list(map(int, input().split()))
    for col in range(N) :
        if cur[col] == 2:
            virus.append((row, col))
    board.append(cur)
flatBoard = list(functools.reduce(lambda x, y : x + y, board, []))
targetCount = len(list(filter(lambda x: x == 0, flatBoard)))
time = 0
dirs = [(1, 0), (0, -1), (0, 1), (-1, 0)]

def next(board, targetCount, virus) :
    curTime = 0
    visited = {}
    for row, col in virus :
        visited[(row, col)] = True
    while targetCount != 0 and virus :
        nextVirus = []
        for row, col in virus :
            for dir in dirs :
                nextRow, nextCol = row + dir[0], col + dir[1]
                if 0 <= nextRow < N and 0 <= nextCol < N and visited.get((nextRow, nextCol)) == None and board[nextRow][nextCol] != 1 :
                    if board[nextRow][nextCol] == 0 :
                        targetCount -= 1    
                    board[nextRow][nextCol] = 2
                    nextVirus.append((nextRow, nextCol))
                    visited[(nextRow, nextCol)] = True
        virus = nextVirus
        curTime += 1
    return curTime if targetCount == 0 else sys.maxsize
res = sys.maxsize
currentVirus = []

def dfs(depth: int, virus) :
    global targetCount, currentVirus, res
    if depth == M :
        copiedBoard = copy.deepcopy(board)
        curTargetCount = targetCount
        curVirus = currentVirus[:]
        res = min(res, next(copiedBoard, curTargetCount, curVirus))
        if res == 0 :
            print(0)
            exit(0)
        return
    virus = copy.deepcopy(virus) 
    while virus :
        curVirus = virus.pop()
        currentVirus.append(curVirus)
        dfs(depth + 1, virus)
        currentVirus.pop()
        
virus = virus[::-1]
dfs(0, virus)
print(res if res != sys.maxsize else -1)