백준 2638번: 치즈
문제
- https://www.acmicpc.net/problem/2638
- BFS/DFS를 활용해 영역 구분하기
기록 포인트
- BFS/DFS가 탐색 과정에서 인접 영역으로 확장되는 특징을 이용해 영역 구분하기
- 문제에서 동일한 공기(0)이더라도, 외부 영역과 치즈에 가로막힌 영역을 구분해야했음
- 이를 위해 외부 영역 중 한 곳(좌측 상단 == (0,0))에서 시작해 인접 셀로 확장해가는 방식으로 외부 영역이 닿는 곳을 확인할 수 있었음
- 탐색 영역을 확장하는 과정에서 주변 체크하기
- 포인트를 정확히 잡기 어려운데, 이 문제에서 외부 공기 영역을 탐색해가며, 해당 외부 공기 셀이 인접한 치즈 셀에 영향을 주었는지를 함께 체크하는 로직이 생각하기 어려웠음
- 지금까지 풀었던 문제들은 A를 기준으로 탐색하면 A만 찾아 탐색 영역에 추가하고 말았는데, 이번 문제는 A를 탐색하는 과정에서 인접한 B까지 함께 처리하는 문제였음
- 타임라인 별로 상태 관리하기
- 타임라인 별로 상태 관리를 하기 위해서는 하나의 시점에 처리할 로직들을 함수화해놓는 편이 편리하고, 로직을 파악하기에도 수월한 것 같음
접근 방식
- 제출 답안 참고
제출 답안
import sys
from collections import deque
N, M = tuple(map(int, sys.stdin.readline().split()))
matrix = []
for _ in range(N):
row = list(map(int, sys.stdin.readline().split()))
matrix.append(row)
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]
# 1단계: 외부 공기를 탐색
# - 반드시 외부 공기인 (0,0) 셀을 시작으로 탐색 가능한 영역까지 확장
# - 이 때, 자연스럽게 외부 공기가 닿은 치즈들을 확인하므로 본인(외부 공기)이 영향을 준 치즈들에 표시
# - 2개 이상의 외부 공기 셀에 영향을 받아야 하므로, 치즈 셀에 영향 받은 횟수를 누적하는 방식으로 진행
# - (이미 탐색 완료한 외부 공기 셀은 다시 방문하지 않도록 처리하므로, 동일한 카운팅이 반복되지 않음)
def update_matrix():
s = (0,0)
parent = {s: None}
queue = deque([s])
while queue:
v1 = queue.popleft()
r1, c1 = v1
for dx, dy in zip(dxs, dys):
r2, c2 = r1+dx, c1+dy
# 존재하는 위치인지 확인
if r2 < 0 or r2 >= N or c2 < 0 or c2 >= M:
continue
v2 = (r2, c2)
# 이미 방문한 셀인지 확인 (외부 공기 셀만 추가되어 있음)
if v2 in parent:
continue
cell = matrix[r2][c2]
# 외부 공기 셀인 경우, 다음 탐색 범위에 추가
if cell == 0:
parent[v2] = v1
queue.append(v2)
# 치즈 셀인 경우, 본인(v1, 외부 공기)이 영향을 주게 되므로 치즈 셀에 +1
else:
matrix[r2][c2] += 1
# 2단계: 영향을 받은 치즈 정리
# - 2개 이상의 외부 공기 셀에 영향을 받은 치즈는 0으로, 그렇지 못한 치즈는 다시 1로 되돌림
# - 이 때, 종료 여부를 판단하기 위해 남아 있는 치즈 개수를 함께 확인
def count_cheese():
cheese_count = 0
for r in range(N):
for c in range(M):
cell = matrix[r][c]
# 영향을 준 외부 공기가 2개 이상인 경우 (1부터 시작하므로 3 이상)
if cell >= 3:
matrix[r][c] = 0
# 영향을 준 외부 공기가 0~1개인 경우, 사라지지 않으므로 다시 1로 되돌림
elif cell >= 1:
matrix[r][c] = 1
# 남은 치즈 개수에 추가
cheese_count += 1
# 외부 공기인 경우(cell == 0) 패스
return cheese_count
cheese_count = count_cheese()
time = 0
while cheese_count:
time += 1
update_matrix()
cheese_count = count_cheese()
print(time)
Author And Source
이 문제에 관하여(백준 2638번: 치즈), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@johnny/baek-2638저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)