[백준] 14502번: 연구소 (파이썬)

✅문제: 14502번

14502번: 연구소

📌개념정리

(1) 너비 우선 탐색(BFS, Breadth-First Search)

• 정의: 그래프의 각 노드를 가까운 노드부터 탐색하는 알고리즘으로, 레벨 별로 탐색을 진행함.
• 파이썬에서는 collections 모듈의 deque를 사용하여 큐 연산을 수행하고, 이를 통해 FIFO(First In First Out) 원칙으로 탐색을 진행함.
• 이 알고리즘은 연구소 문제에서 바이러스의 확산을 모델링하는 데 사용됨.

📌문제풀이

연구소 내에서 바이러스의 확산을 막기 위해 벽을 세워 안전 영역의 최대 크기를 찾는 문제임.

1. 연구소에서 벽을 세울 수 있는 모든 위치의 조합을 생성하여 각 조합에 대해 벽을 세움
2. BFS를 이용하여 바이러스가 퍼질 수 있는 영역을 시뮬레이션하고, 바이러스 퍼진 후의 안전 영역 크기를 계산
3. 모든 조합에 대해 안전 영역의 크기를 비교하여 가장 큰 값을 찾음

from itertools import combinations
from copy import deepcopy
from collections import deque

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

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(virus_map):
    queue = deque()
    # 초기 바이러스 위치를 큐에 추가
    for i in range(n):
        for j in range(m):
            if virus_map[i][j] == 2:
                queue.append((i, j))
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and virus_map[nx][ny] == 0:
                virus_map[nx][ny] = 2
                queue.append((nx, ny))
    
    # 안전 영역 크기 계산
    safe_count = sum(row.count(0) for row in virus_map)
    return safe_count

# 벽을 세울 수 있는 위치 찾기
empty_spaces = [(i, j) for i in range(n) for j in range(m) if lab[i][j] == 0]
max_safe_area = 0

# 모든 가능한 벽 3개의 조합에 대해 시뮬레이션
for walls in combinations(empty_spaces, 3):
    test_lab = deepcopy(lab)
    # 벽 세우기
    for x, y in walls:
        test_lab[x][y] = 1
    # 바이러스 퍼뜨리기 및 안전 영역 계산
    max_safe_area = max(max_safe_area, bfs(test_lab))

print(max_safe_area)

문제 이해를 위해 예제 입력 1의 실행 결과를 단계별로 정리해보겠음. 7x7 격자 형로 주어진 숫자는 다음과 같음.

• '2'는 바이러스가 있는 위치임.
• '1'은 이미 세워진 벽을 나타냄.
• '0'은 비어 있는 칸이고, 벽을 세울 수 있음.

# 예제 입력 1(바이러스 초기 상태)
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

1) 벽을 세울 수 있는 위치 찾기 (0의 위치)

비어있는 칸(0)을 모두 찾아 벽을 세울 수 있는 위치의 목록을 만듦. 예제에 36개의 빈 칸이 있음.

• (0,1), (0,2), (0,3), (0,6)
• (1,0), (1,1), (1,3), (1,6)
• (2,0), (2,2), (2,3), (2,5), (2,6)
• (3,0), (3,2), (3,3), (3,4), (3,5), (3,6)
• (4,0), (4,1), (4,2), (4,3), (4,4)
• (5,0), (5,2), (5,3), (5,4), (5,5), (5,6)
• (6,0), (6,2), (6,3), (6,4), (6,5), (6,6)

2) 벽 세우기의 모든 조합 시뮬레이션

itertools.combinations를 이용하여 36개의 빈 칸 중 3개를 선택하는 모든 조합을 생성함. 총 조합의 수는 
𝐶(36, 3) = 7140개임.

 

3) 바이러스 확산 시뮬레이션 (BFS)

1. 초기 바이러스 위치는 (0,0)과 (1,5)에서 시작하여 BFS를 수행함.
2. 각 바이러스 위치에서 상하좌우로 인접한 빈 칸으로 바이러스를 확산시키며, 벽(1)에는 확산되지 않음.
3. 큐를 통해 모든 가능한 바이러스 확산이 완료될 때까지 반복함.

 

4) 안전 영역 계산
BFS 확산 후 남은 빈 칸(0)의 개수를 세어 안전 영역의 크기를 계산함. 모든 조합에 대해 계산된 안전 영역 중 최대값을 찾음.

 

임의로 예제 출력 1이 나올 수 있는 방법을 생각하면 다음과 같음.

• 가정한 벽 위치: (1,2), (2,1), (5,6)

# 바이러스 확산 전
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

# 바이러스 확산 후
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

5) 최적 조합 확인

입력된 격자와 바이러스 위치에서 최적의 벽 배치를 통해 계산된 최대 안전 영역은 27칸임.

# 예제 출력 1
27

📌후기

• 난이도가 있는 문제답게 이해하는 데 어려웠음. BFS와 조합을 적절히 활용해야 해결하는 문제로, 해결하기 위해 많은 시간이 들었음.
• 처음 사용해보는 모듈들을 이용해 코드를 구현함. 딥 카피(deepcopy)를 사용해 초기 맵의 상태를 보존했음.

📌참고자료

1) 위키독스, "008 앞뒤에서 자료를 넣고 빼려면? ― collections.deque", https://wikidocs.net/104977
2) 위키독스, "12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)", https://wikidocs.net/16038
3) 위키독스, "028 로또의 모든 가짓수를 구하려면? ― itertools.combinations", https://wikidocs.net/106964