https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
1. check_melt : 얼음이 다 녹았는지 확인하고 전체가 0이면 0을 출력
2. count_zero : 빙산이 있으면 그 주변으로 0의 개수를 확인
-> 이때 주의해야 할 것은 항상 원본 데이터로 0의 개수를 세어야한다. 그래서 new_data를 만들고 업데이트
3. bfs : bfs로 빙산 덩어리가 몇개인지 확인
from collections import deque
from copy import deepcopy
n,m = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def count_zero(x,y):
cnt = 0
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m and data[nx][ny]==0:
cnt += 1
return cnt
def bfs(x,y):
q = deque()
q.append((x,y))
visit = [[0] * m for _ in range(n)]
visit[x][y] = 1
while q:
x,y = q.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m and visit[nx][ny]==0 and new_data[nx][ny]!=0:
visit[nx][ny] = 1
new_data[nx][ny] = 0
q.append((nx,ny))
def check_melt():
for i in range(n):
for j in range(m):
if data[i][j] != 0:
return False
return True
year = 0
while 1:
year += 1
if check_melt():
print(0)
break
new_data = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if data[i][j] != 0:
zero = count_zero(i,j)
value = data[i][j] - zero
new_data[i][j] = value if value >= 0 else 0
data = deepcopy(new_data)
cnt = 0
for i in range(n):
for j in range(m):
if new_data[i][j] != 0:
bfs(i,j)
cnt += 1
if cnt >= 2:
print(year)
break
'알고리즘' 카테고리의 다른 글
백준 1021번 : 회전하는 큐 (Python) (0) | 2021.02.03 |
---|---|
백준 17135번 : 캐슬 디펜스 (Python) (0) | 2021.01.25 |
백준 1012번 : 유기농 배추(python) (0) | 2021.01.05 |
백준 2178번 : 미로 탐색(python) (0) | 2021.01.05 |
백준 7562번 : 나이트의 이동(python) (0) | 2021.01.05 |