*문제 출처는 백준에 있습니다.

문제 제목: 빙산 / 2573번 (골드 4단계)
문제 사이트: https://www.acmicpc.net/problem/2573
문제 설명

나의 풀이
import sys
from collections import deque
input = sys.stdin.readline
def solution(n, m, ice):
answer = 0
directions = [(-1,0),(1,0),(0,-1),(0,1)]
# 빙산이 있는 좌표만 저장
ice_coords = [(i,j) for i in range(n) for j in range(m) if ice[i][j] > 0]
while True:
# 1. 빙산 덩어리 수 세기 (BFS)
visited = [[False]*m for _ in range(n)]
chunks = 0
for i, j in ice_coords:
if not visited[i][j]:
chunks += 1
if chunks >= 2:
return answer
q = deque()
q.append((i,j))
visited[i][j] = True
while q:
y, x = q.popleft()
for dy, dx in directions:
ny, nx = y+dy, x+dx
if 0 <= ny < n and 0 <= nx < m:
if not visited[ny][nx] and ice[ny][nx] > 0:
visited[ny][nx] = True
q.append((ny, nx))
if chunks == 0:
return 0
# 2. 녹을 양 계산
melt = [[0]*m for _ in range(n)]
for y, x in ice_coords:
sea = 0
for dy, dx in directions:
ny, nx = y+dy, x+dx
if 0 <= ny < n and 0 <= nx < m and ice[ny][nx] == 0:
sea += 1
melt[y][x] = sea
# 3. 얼음 녹이기 & 얼음 있는 좌표 업데이트
new_ice_coords = []
for y, x in ice_coords:
ice[y][x] = max(0, ice[y][x] - melt[y][x])
if ice[y][x] > 0:
new_ice_coords.append((y,x))
ice_coords = new_ice_coords
answer += 1
def main():
n, m = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(n)]
print(solution(n, m, ice))
if __name__ == "__main__":
main()

※ 알아야 할 것
def solution(n, m, ice):
answer = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 우 좌 하 상
while True:
# 1. 빙산 녹는 양 계산
visited = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if ice[i][j] > 0:
for dy, dx in move:
ny, nx = i + dy, j + dx
if 0 <= ny < n and 0 <= nx < m:
if ice[ny][nx] == 0:
visited[i][j] += 1
# 2. 빙산 녹이기 적용
for i in range(n):
for j in range(m):
ice[i][j] = max(0, ice[i][j] - visited[i][j])
# 3. 빙산 덩어리 수 세기 (BFS)
count = 0
checked = [[False] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if ice[i][j] > 0 and not checked[i][j]:
count += 1
if count >= 2:
return answer + 1
# BFS 시작
q = deque()
q.append((i, j))
checked[i][j] = True
while q:
y, x = q.popleft()
for dy, dx in move:
ny, nx = y + dy, x + dx
if 0 <= ny < n and 0 <= nx < m:
if ice[ny][nx] > 0 and not checked[ny][nx]:
q.append((ny, nx))
checked[ny][nx] = True
# 4. 전부 다 녹았는지 체크
if all(ice[i][j] == 0 for i in range(n) for j in range(m)):
return 0
answer += 1
위는 시간초과가 발생하는 알고리즘입니다!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 스티커 / 9465번 / Python (0) | 2025.06.27 |
|---|---|
| 백준 / 컨베이어 벨트 위의 로봇 / 20055번 / Python (0) | 2025.06.23 |
| 백준 / 모든 순열 / 10974번 / Python (0) | 2025.06.14 |
| 백준 / 쇠막대기 / 10799번 / Python (0) | 2025.06.12 |
| 백준 / 제곱수의 합 / 1699번 / Python (0) | 2025.06.10 |