이번에 풀어야 할 문제는 빙산 문제입니다. 입력으로 주어진 빙산은 시간이 지남에 따라 녹는데 문제는 빙산이 처음 분리된 시간을 찾는 것이다. 문제의 상태는 다음과 같습니다.
- 빙산은 수직과 수평으로 닿는 바닷물 기둥의 수만큼 녹는다.
- 빙산이 차지하는 최대 사각형 수는 10,000개입니다.
- 배열의 첫 번째와 마지막 행, 첫 번째와 마지막 열에는 빙산이 없습니다.
- 빙산의 높이는 최대 10입니다.
이것은 근본적인 검색 문제입니다. 먼저 바닷물과 접촉하고 있는 빙산을 녹인 다음 아직 녹지 않은 빙산을 탐색하고 연결된 모든 빙산을 방문한다. 1회 검색 후에도 아직 방문하지 않은 빙산이 있는 경우 빙산이 2개 이상으로 나뉘므로 검색을 종료한다.
그러나 이 문제를 해결할 때 고려해야 할 몇 가지 사항이 있습니다.
- 빙산을 녹일 때 동시에 녹는 빙산은 다른 빙산이 녹는 속도에 영향을 미치지 않아야 합니다.
- 빙산이 두 개 이상의 부분으로 분리되지 않고 한 번에 녹는 경우가 있습니다.
사례 1은 아래 그림과 같습니다.
위의 상황을 가정해 봅시다. 이제 바닷물에 닿은 빙산이 녹고 있습니다.낙하량을 다음과 같이 계산합니다.
위의 상황에서 이제 빙산을 하나씩 조사하고 고도뿐만 아니라 삭제할 수 있습니다. 그러나 구현 시 빙산에 인접한 해수 셀의 수를 세어 빙산을 즉시 삭제하는 경우가 있어 다음과 같은 상황이 발생할 수 있습니다.
이 이미지는 이전 이미지의 상단에서 빙산과 접한 해수 구획을 세고 그 양을 삭제한 결과입니다. 가운데 1도 좌측 1이 삭제된 후 해수시험을 진행하기 때문에 좌측하단의 3도 해수구획을 기존 2개에서 3개로 늘려 삭제하였다. 이와 같은 구현은 완전히 잘못된 답변으로 이어질 수 있습니다.
두 번째 문제는 위의 그림과 동일합니다. 아직은 빙산의 한 조각에 불과하지만 시간이 지나면 모든 빙산이 녹아내릴 것입니다. 문제는 이 경우 0을 반환하므로 이를 결정해야 한다고 말합니다.
이제 코드를 하나씩 살펴보겠습니다.
dic = {}
for i in range(n):
for j in range(m):
if world(i)(j) > 0:
dic((i, j)) = world(i)(j)먼저 빙산의 위치를 찾고 위치를 키 값으로, 빙산 높이를 값으로 하는 사전을 만듭니다.
time = 1
while True:
loop = list(dic.keys())
# 빙산이 녹아내리는 값 계산
for y, x in loop:
cnt = 0
for d in range(4):
ny, nx = y+dy(d), x+dx(d)
if 0 <= ny < n and 0 <= nx < m:
if world(ny)(nx) == 0:
cnt += 1
dic((y,x)) -= cnt
# 빙산을 실제로 녹임
not_exist = True
for y, x in loop:
if dic((y, x)) <= 0:
world(y)(x) = 0
dic.pop((y, x))
else:
not_exist = False
if not_exist:
print(0)
break
# 빙산이 분리되었는지 검사
visited = ((0) * m for _ in range(n))
cnt_bfs = 0
for y, x in dic.keys():
if not visited(y)(x):
if cnt_bfs == 1:
cnt_bfs += 1
break
bfs(y, x, visited)
cnt_bfs += 1
if cnt_bfs > 1:
print(time)
break
time += 1그리고 while 문 내에서 시간을 1씩 증가시켜 빙산의 녹는 값을 순서대로 계산하고 계산된 값을 기준으로 실제 빙산을 녹이고 최종적으로 빙산이 분리되었는지를 확인한다. 사전이 비어 있으면 not_exist 변수가 true로 설정되고 0이 인쇄된 후 종료됩니다. BFS는 빙산이 연결되어 있는지 검색하는 데 사용되었습니다.
마지막으로 전체 코드는 다음과 같습니다.
import sys
from collections import deque
input = sys.stdin.readline
dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)
n, m = map(int, input().split())
world = (list(map(int, input().split())) for _ in range(n))
def bfs(y, x, visited):
deq = deque()
deq.append((y, x))
while deq:
y, x = deq.popleft()
for i in range(4):
ny, nx = y+dy(i), x+dx(i)
if 0 <= ny < n and 0 <= nx < m:
if not visited(ny)(nx) and world(ny)(nx) > 0:
visited(ny)(nx) = 1
deq.append((ny, nx))
dic = {}
for i in range(n):
for j in range(m):
if world(i)(j) > 0:
dic((i, j)) = world(i)(j)
time = 1
while True:
loop = list(dic.keys())
for y, x in loop:
cnt = 0
for d in range(4):
ny, nx = y+dy(d), x+dx(d)
if 0 <= ny < n and 0 <= nx < m:
if world(ny)(nx) == 0:
cnt += 1
dic((y,x)) -= cnt
not_exist = True
for y, x in loop:
if dic((y, x)) <= 0:
world(y)(x) = 0
dic.pop((y, x))
else:
not_exist = False
if not_exist:
print(0)
break
visited = ((0) * m for _ in range(n))
cnt_bfs = 0
for y, x in dic.keys():
if not visited(y)(x):
if cnt_bfs == 1:
cnt_bfs += 1
break
bfs(y, x, visited)
cnt_bfs += 1
if cnt_bfs > 1:
print(time)
break
time += 1