백준
백준 2573 빙산 (파이썬)
chldkato
2020. 2. 17. 01:19
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지
www.acmicpc.net
1. 빙산이 있는 위치에서 상하좌우에 물(0)의 개수만큼 빙산을 녹인다. 이 때 0보다 작아지면 안된다
2. 빙산이 녹은 뒤 bfs로 몇 개로 분리되었는지 구한다
3. 2개 이상이면 걸린 시간을 출력, 분리되지 않으면 더 이상 분리할 수 없을 때까지 과정 반복
from collections import deque
import sys, copy
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
q.append([x, y])
c[x][y] = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if na[nx][ny] != 0 and c[nx][ny] == 0:
c[nx][ny] = 1
q.append([nx, ny])
def ice():
a2 = copy.deepcopy(a)
for i in range(n):
for j in range(m):
if a[i][j] != 0:
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if 0 <= nx < n and 0 <= ny < m:
if a[nx][ny] == 0:
a2[i][j] -= 1
if a2[i][j] == 0:
break
return a2
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
q = deque()
year = 1
while True:
na = ice()
flag = 0
for i in na:
flag += i.count(0)
if flag == n*m:
print(0)
sys.exit()
a = copy.deepcopy(na)
c = [[0]*m for _ in range(n)]
cnt = 1
for i in range(n):
for j in range(m):
if na[i][j] != 0 and c[i][j] == 0:
if cnt == 2:
print(year)
sys.exit()
bfs(i, j)
cnt += 1
year += 1