[백준] 17141 : 연구소2 (Python)

 

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

 

---

 

아이디어

'상하좌우로 인접한 모든 빈칸으로 동시에 복제'

해당 요구사항을 통해, 동시에 인접한 칸들로 복제되므로 BFS 그래프 탐색 유형임을 알 수 있다. 그렇다면, 이를 토대로 구현에 필요한 핵심 인사이트들을 파악해보자.

 

바이러스가 모든 빈 칸들에 복제되었는지 어떻게 판단할까?

모든 빈 칸들이 복제되었는지에 대한 여부를 판단해야하므로, 빈 칸 카운팅이 필요하다는 것을 알 수 있다. 즉, BFS 탐색 전의 빈칸들 상태와 탐색 후 빈칸들 상태를 같은지 비교하면 된다.

이를 위해 다음 2가지 카운팅 변수를 설정해야 한다.

• Total_blank : 초기 연수소의 빈칸(0)의 개수들을 카운팅 + 바이러스 후보 칸들(2)
• State_blank : BFS 탐색 중, 다음 탐색 대상인 자식노드들 카운팅
• 여부 판단 조건 : IF Total_blank - m == State_blank

이 때, m을 빼는 이유는 m개의 칸들에 바이러스를 배치한 상태로 복제가 시작되기 때문이다.

 

m개의 바이러스를 배치하는 경우의 수는 어떻게 구해야할까?

먼저, 바이러스 후보 칸(2)들을 파악하여, Candidates 배열에 인덱스(x,y)를 저장한다. 이를 토대로, 경우의 수(상태)는 다음 2가지 중 하나로 구할 수 있다.

백트래킹(DFS)

백트래킹으로 바이러스 배치 경우의 수를 구하는 과정 시각화

문제에서 요구한 m 그래프 깊이에 도달할 때마다, BFS를 통해 바이러스 복제 시뮬레이션을 진행하는 과정이다. 그래프에 대한 의미는 다음과 같이 정리하였다.

• Node : 바이러스 인덱스 튜플
• Depth : 몇 개의 바이러스인가 (m)

즉, 현재 타겟까지의 경로를 저장시킨 배열을 통해 bfs의 인자로 삽입하면, 해당 상황에서의 바이러스 복제 여부를 판단할 수 있게 된다.

 

조합(Combination)

파이썬 라이브러리인 combination을 통해, 미리 모든 경우의 수를 파악해놓고, 각 경우들을 BFS 탐색을 진행하여 정답 갱신을 하는 방식이다.

필자는 조합 방식으로 프로그램을 구현하였다.

 

각 경우들의 시간은 어떻게 측정할까?

결론부터 말하자면, 그래프 깊이는 복제 시간과 동일하다. 다음의 시각화 과정을 통해 알아보자.

BFS 탐색 과정 시각화

초기 바이러스를 배치한 후에, BFS 탐색이 시작된다.

부모 노드로부터 다음 2가지의 조건에 부합하는 자식노드들을 다음 탐색 대상으로 삼게 된다.

1. 자식 노드는 빈칸(0) 또는 바이러스 후보 탈락칸(2) 인가?
2. 방문하지 않은 자식 노드인가?

이는 인접한 칸들에 복제를 함으로써, 시간 관점에서는 +1이 되고, 그래프 관점에서는 깊이가 +1이 된다는 의미이다. 그러므로, 그래프의 깊이를 통해 시간을 구할 수 있고, 이를 위한 deque를 다음과 같이 설정 가능하다.

• 초기 deque = [(x,y,0), ..., m개]
• x,y : 해당 바이러스가 배치된 인덱스 행과 열
• 0 : 현재 그래프 깊이(시간)

또한, 이 BFS 탐색 과정 시, State_blank 카운팅 변수를 통해 선택된 자식노드들의 개수를 해당 변수에 더해주면 된다. 이후, BFS 탐색 종료 시 초기 빈칸들의 개수(Total_blank)와 비교해준다.

 

정답 코드

# https://www.acmicpc.net/problem/17141
# 연구소2
# 그래프탐색, bfs, 브루트포스

from sys import stdin 
from collections import deque
from itertools import combinations
input=stdin.readline

def bfs(init_virus):
    q=deque([(x,y,0) for x,y in init_virus]) # virus_idx_x, virus_idx_y, time(==depth)
    visited=[[0]*n for _ in range(n)]
    for x,y in init_virus:
        visited[x][y]=1
    
    state_blank,state_time=0,0 # 바이러스가 복제된 빈칸 개수, 바이러스가 퍼지는데 걸리는 시간
    while q:
        x,y,depth=q.popleft()
        state_time=max(state_time,depth)
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<n and 0<=ny<n:
                if board[nx][ny]!=1 and visited[nx][ny]==0:
                    visited[nx][ny]=1
                    q.append((nx,ny,depth+1))
                    state_blank+=1 # 해당 자식노드 복제 처리
    
    # 모든 빈칸에 복제가 되었는가
    return state_time, [False,True][state_blank==total_blank-m]

n,m=map(int,input().split())
candidates,board=[],[] # 바이러스 후보 칸들, 연구소
total_blank=0 # 초기 빈칸들의 개수
answer=-1

for i in range(n):
    tmp=[*map(int,input().split())]
    for j in range(n):
        if tmp[j]==2:
            candidates.append((i,j))
        if tmp[j]!=1: # 바이러스 후보 칸도 복제가 가능.
            total_blank+=1
    board.append(tmp)

# 바이러스 배치 경우들을 하나씩 조회
for cur_candidate in combinations(candidates,m):
    time,flag=bfs(cur_candidate) # 해당 배치 경우에서 복제 시뮬레이션 실행
    # 모든 빈칸들에 복제가 되었다면
    if flag:
        if answer==-1:
            answer=time
        else:
            answer=min(answer,time)

print(answer)