문제 이해
1년이 지날때마다, 주위의 바닷물의 개수만큼 빙산의 높이가 감소한다.
빙산덩어리란 빙산이 상하좌우로 이어져있다면 이를 빙산 덩어리라고 한다.
빙산 덩어리의 개수가 몇년이 지나야 2개 이상이 되는가?
만약 빙산이 다 녹을때까지 2개 이상이 되지 않는다면 0을 출력해라
아래의 그림 1은 초기값이고 그림 2는 1년 후 그림 3은 2년 후이다.
따라서 예제에서의 정답은 2년 후이다.
문제 접근
아래의 3가지 단계로 나누어 문제에 접근했다.
우선 인접해있는 칸 수를 확인하고 이를 2차원 배열에 넣어둔다. 바로 높이를 빼줄 경우에 다음 빙산에게 영향이 갈 수 있기 때문에 저장해둔 후에 한번에 빼주도록 한다.
그렇게 인접해있는 칸 수 만큼 녹이고, 덩어리가 몇개인지를 확인해야 하는데, 이를 BFS로 확인해주었다.
- 인접해있는 칸 수 확인하기
- 인접해있는 칸 수 만큼 녹이기
- 덩어리가 몇개인지 확인하기(BFS)
문제 풀이
인접해있는 칸 수 확인하기
melt라는 함수를 생성한다. melt는 좌표 x,y의 상하좌우를 탐색하여 바다인지 확인하고 바다일 경우에 around_sea라는 2차원 배열에 그 값을 저장하는 함수이다.
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def melt(x,y): # 인접해있는 칸 수 확인하기
for t in range(4):
nx = x + dx[t]
ny = y + dy[t]
if nx<0 or ny<0 or nx>=N or ny>=M:
continue
if sea[nx][ny]==0:
around_sea[x][y]+=1아래는 main함수에서의 코드이다.
빙산의 좌표를 melt에 넣어준다. 그와 동시에 빙산의 개수를 count해 빙산이 다 녹았다면 0을 출력하도록 한다.
for i in range(N): # 바닷물 인접 개수 구하기
for j in range(M):
if sea[i][j] > 0:
count += 1 # 남아있는 얼음 개수 확인
melt(i,j) # i,j의 인접한 칸수 확인
if count == 0: # 다 녹을때까지 반복문 벗어나지 못했으므로 0 출력
print(0)
break인접해있는 칸 수 만큼 녹이기
인접해있는 칸 수를 확인했으니 이제 빙산을 녹여준다. 빙산의 높이는 0 미만으로 내려갈 수 없으므로 그럴 경우 0을 넣는다.
for i in range(N): # 인접 개수만큼 녹이기
for j in range(M):
if sea[i][j] > around_sea[i][j]:
sea[i][j]-=around_sea[i][j]
around_sea[i][j] = 0 # 녹이고 다시 초기화
else:
sea[i][j] = 0
around_sea[i][j] = 0 # 녹이고 다시 초기화덩어리가 몇개인지 확인하기(BFS)
bfs를 통해 덩어리의 개수를 확인한다. visited를 선언하여 여기에 덩어리의 개수를 넣는다.
만약 덩어리의 개수가 3개라면 visited에는 1,2,3의 값들이 들어있겠다.
def bfs(i,j): # 덩어리가 몇 개인지 확인하기
q = deque()
global temp
q.append((i,j))
temp += 1
while q:
x,y = q.popleft()
for t in range(4):
nx = x + dx[t]
ny = y + dy[t]
if nx<0 or ny<0 or nx>=N or ny>=M:
continue
if sea[nx][ny]!=0 and visited[nx][ny]==0:
q.append((nx,ny))
visited[nx][ny] = tempmain함수에서는 빙산이 존재하고 방문한적이 없다면(빙산덩어리에 카운트 되지 않았다면) bfs를 실행하도록 한다.
for i in range(N): # 덩어리의 개수 구하기
for j in range(M):
if sea[i][j]>0 and visited[i][j]==0: # 방문한적 없고, 얼음이 있으면 bfs실행하여 덩어리 확인
bfs(i,j) # 덩어리 개수 확인 temp에제출 코드
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
sea = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# 인접해있는 칸 수 확인하기
# 인접해있는 칸 수 만큼 녹이기
# 덩어리가 몇개인지 확인하기
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def melt(x,y): # 인접해있는 칸 수 확인하기
for t in range(4):
nx = x + dx[t]
ny = y + dy[t]
if nx<0 or ny<0 or nx>=N or ny>=M:
continue
if sea[nx][ny]==0:
around_sea[x][y]+=1
def bfs(i,j): # 덩어리가 몇 개인지 확인하기
q = deque()
global temp
q.append((i,j))
temp += 1
while q:
x,y = q.popleft()
for t in range(4):
nx = x + dx[t]
ny = y + dy[t]
if nx<0 or ny<0 or nx>=N or ny>=M:
continue
if sea[nx][ny]!=0 and visited[nx][ny]==0:
q.append((nx,ny))
visited[nx][ny] = temp
around_sea = [[0 for _ in range(M)] for _ in range(N)]
year = 0
while True:
temp = 0
count = 0
year += 1
visited = [[0 for _ in range(M)] for i in range(N)]
for i in range(N): # 바닷물 인접 개수 구하기
for j in range(M):
if sea[i][j] > 0:
count += 1 # 남아있는 얼음 개수 확인
melt(i,j) # i,j의 인접한 칸수 확인
if count == 0: # 다 녹을때까지 반복문 벗어나지 못했으므로 0 출력
print(0)
break
for i in range(N): # 인접 개수만큼 녹이기
for j in range(M):
if sea[i][j] > around_sea[i][j]:
sea[i][j]-=around_sea[i][j]
around_sea[i][j] = 0 # 녹이고 다시 초기화
else:
sea[i][j] = 0
around_sea[i][j] = 0 # 녹이고 다시 초기화
for i in range(N): # 덩어리의 개수 구하기
for j in range(M):
if sea[i][j]>0 and visited[i][j]==0: # 방문한적 없고, 얼음이 있으면 bfs실행하여 덩어리 확인
bfs(i,j) # 덩어리 개수 확인 temp에
if temp>=2:
print(year)
break
