[Baekjoon] 17141번: 연구소 2(DFS/BFS Gold4) - Python

1. 문제

연구소 2

2. 코드

from collections import deque
from itertools import combinations

def bfs(start, count):
    queue = deque()
    visited = [[0] * n for _ in range(n)]

    for sx, sy in start:
        queue.append((sx, sy, 0))
        visited[sx][sy] = 1

    while queue:
        cx, cy, time = queue.popleft()
        if count == 0: 
            break
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < n and lab[nx][ny] != 1 and visited[nx][ny] == 0:
                queue.append((nx, ny, time+1))
                visited[nx][ny] = 1
                count -= 1  
    if count == 0:
        return time
              
    return float('inf')

n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]

virusPoint = deque()
minTime = float('inf')
count = 0

for x in range(n):
    for y in range(n):
        if lab[x][y] == 2:
            virusPoint.append((x, y))
            count += 1
        elif lab[x][y] == 0:
            count += 1

count -= m

for start in combinations(virusPoint, m):
    minTime = min(minTime, bfs(start, count))
    if minTime == 3:
      print(start)
  
print(-1 if minTime == float('inf') else minTime)

3. 로직

메인 함수

1. 입력 받기: 연구소의 크기와 초기 상태를 입력 받는다.

2. 바이러스와 빈 칸 개수 계산:

• virusPoint: 바이러스가 있는 위치를 저장할 리스트.
• count: 바이러스와 빈 칸의 개수를 세는 변수.
• 모든 위치를 순회하면서 바이러스가 있는 위치는 virusPoint에 추가하고, 빈 칸의 경우 count를 증가시킨다.
• 이 때, 초기 상태에서 바이러스와 빈 칸의 위치를 파악한다.

3. 바이러스를 놓을 수 있는 조합 생성:

• combinations(virusPoint, m)를 사용하여 바이러스가 있는 위치 중에서 m개를 선택하는 모든 조합을 생성한다.

4. 조합별 최소 시간 계산:

• 생성된 각 조합에 대해 다음을 수행한다.:
  • bfs(start, count) 함수 호출로 최소 시간을 계산한다.
  • 바이러스를 놓을 수 있는 경우에 대해 바이러스를 퍼뜨리는 시간을 계산한다.
  • 이 때, count를 활용하여 모든 빈 칸에 바이러스를 퍼뜨릴 수 있는지 확인한다.

5. 최소 시간 및 조합 출력:

• 모든 조합에 대해 최소 시간을 계산하고, 그 중에서 최소 시간을 출력한다.

bfs 함수

1. queue 초기화 및 방문 배열(visited) 초기화:

• queue: BFS를 위한 큐이다.
• visited: 해당 위치를 이미 방문했는지 여부를 저장하는 배열이다.
• start에 있는 위치들을 큐에 추가하고, 해당 위치를 방문했음을 표시한다.

2. BFS 탐색:

• 큐가 빌 때까지 다음을 반복한다.
  • 큐에서 원소를 하나 꺼내서 현재 위치(cx, cy)와 시간(time)을 얻는다.
  • 상하좌우 인접한 위치를 확인하면서 바이러스가 퍼질 수 있는지 체크한다.
  • 조건에 맞으면 해당 위치를 큐에 추가하고, 방문했음을 표시한다.

3. 바이러스가 모든 빈 칸에 퍼지는지 확인:

• 모든 빈 칸에 바이러스가 퍼졌는지 확인하기 위해 count를 활용한다.
• 모든 빈 칸에 바이러스가 퍼진 경우, 최종 시간(time)을 반환한다.

4. 바이러스가 모든 빈 칸에 퍼지지 않는 경우:

• 모든 빈 칸에 바이러스를 퍼뜨리지 못한 경우 float('inf')를 반환한다.