일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 부트캠프
- UXUI챌린지
- Be
- 구현
- 백엔드 부트캠프
- knu
- 환급챌린지
- 백준
- 코드스테이츠
- 백엔드개발자
- 기초
- 국비지원교육
- js
- 내일배움카드
- 직무역량캠프
- OPENPATH
- 문자열
- UXUI기초정복
- 오픈패스
- 패스트캠퍼스
- 오픈챌린지
- UXUIPrimary
- 디자인교육
- 디자인챌린지
- 디자인강의
- baekjoon
- KDT
- 국비지원취업
- 국비지원
- javascript
- Today
- Total
군만두의 IT 공부 일지
[백준] 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)
- 초기 바이러스 위치는 (0,0)과 (1,5)에서 시작하여 BFS를 수행함.
- 각 바이러스 위치에서 상하좌우로 인접한 빈 칸으로 바이러스를 확산시키며, 벽(1)에는 확산되지 않음.
- 큐를 통해 모든 가능한 바이러스 확산이 완료될 때까지 반복함.
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
'코딩테스트 > 백준' 카테고리의 다른 글
[백준] 1717번: 집합의 표현 (파이썬) (0) | 2024.04.25 |
---|---|
[백준] 1068번: 트리 (파이썬) (0) | 2024.04.23 |
[백준] 25206번: 너의 학점은 (파이썬) (0) | 2024.04.21 |
[백준] 7795번: 먹을 것인가 먹힐 것인가 (파이썬) (0) | 2024.04.17 |
[백준] 2230번: 수 고르기 (파이썬) (0) | 2024.04.14 |