이번 문제는 너비 우선 탐색을 통해 해결하였다. 로직은 맞게 작성했지만 시간 초과 이슈가 계속 발생하여서 여러번 접근 방식을 변경하였다.

우선 처음으로 접근했을 때는 빙산이 녹는 함수는 BFS로, 빙산의 개수를 세는 함수는 DFS로 작성하였다. 매 while문마다 0으로 채워진 새로운 그래프를 선언하고, BFS에서 녹은 빙산의 높이를 새로운 그래프에 넣도록 하였다. (한번에 녹은 것을 구현하기 위함) 원하는 답은 잘 구해졌지만 시간초과가 발생하였다.

import sys
from collections import deque
sys.setrecursionlimit(10**6)
n, m=map(int, input().split())
ocean=[]
for _ in range(n):
    ocean.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
def bfs(q):
    while q:
        y, x=q.popleft()
        cnt=0
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m:
                if ocean[ny][nx]<=0:
                    cnt+=1
        ocean2[y][x]=ocean[y][x]-cnt
def dfs(y, x):
    chk[y][x]=True
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<n and 0<=nx<m and not chk[ny][nx] and ocean[ny][nx]>0:
            dfs(ny, nx)
answer=0
cnt=0
while cnt<2:
    answer+=1
    chk=[[False]*m for _ in range(n)]
    dq=deque()
    ocean2 = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if ocean[i][j]>0:
                dq.append((i, j))
    bfs(dq)
    ocean=ocean2.copy()
    cnt=0
    for i in range(n):
        for j in range(m):
            if ocean[i][j]>0 and not chk[i][j]:
                dfs(i, j)
                cnt+=1
            if cnt>=2:
                print(answer)
                quit()

생각해보니 빙산이 녹는 것을 굳이 BFS로 안해도 되겠다는 생각이 들었다. 그래서 빙산이 녹는 함수를 if문을 여러개 사용하여 작성하였고, 빙산의 개수를 세는 함수는 DFS를 그대로 사용하였다. 이 풀이 역시 시간초과가 발생하였다.

import sys
from collections import deque
sys.setrecursionlimit(10**5)
input=sys.stdin.readline
n, m=map(int, input().split())
ocean=[]
for _ in range(n):
    ocean.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
def melt():
    for y in range(n):
        for x in range(m):
            if ocean[y][x]>0:
                cnt=0
                for i in range(4):
                    ny=y+dy[i]
                    nx=x+dx[i]
                    if 0 <= ny < n and 0 <= nx < m:
                        if ocean[ny][nx] <= 0:
                            cnt += 1
                ocean2[y][x] = ocean[y][x] - cnt
def dfs(y, x):
    chk[y][x]=True
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<n and 0<=nx<m and not chk[ny][nx] and ocean[ny][nx]>0:
            dfs(ny, nx)
answer=0
cnt=0
while cnt<2:
    answer+=1
    chk=[[False]*m for _ in range(n)]
    ocean2=[[0]*m for _ in range(n)]
    melt()
    ocean=ocean2.copy()
    cnt=0
    for i in range(n):
        for j in range(m):
            if ocean[i][j]>0 and not chk[i][j]:
                dfs(i, j)
                cnt+=1
            if cnt>=2:
                print(answer)
                quit()

보통 DFS보다 BFS의 성능이 조금 더 좋으므로 빙하의 개수를 세는 함수를 BFS로 다시 작성하여 제출하였다. 그러나 이번에도 시간 초과가 발생하였다.

import sys
from collections import deque
input=sys.stdin.readline
n, m=map(int, input().split())
ocean=[]
for _ in range(n):
    ocean.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
def bfs(s_y, s_x):
    q=deque()
    q.append((s_y, s_x))
    chk.add((s_y, s_x))
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m and ocean[ny][nx]>0 and (ny, nx) not in chk:
                chk.add((ny, nx))
                q.append((ny, nx))

def melt():
    for y in range(n):
        for x in range(m):
            if ocean[y][x]>0:
                cnt=0
                if ocean[y-1][x]<=0:
                    cnt+=1
                if ocean[y+1][x]<=0:
                    cnt+=1
                if ocean[y][x-1]<=0:
                    cnt+=1
                if ocean[y][x+1]<=0:
                    cnt+=1
                ocean2[y][x]=ocean[y][x]-cnt
answer=0
cnt=0
while cnt<2:
    answer+=1
    chk=set()
    ocean2=[[0]*m for _ in range(n)]
    melt()
    ocean=ocean2.copy()
    cnt=0
    for i in range(n):
        for j in range(m):
            if ocean[i][j]>0 and (i, j) not in chk:
                bfs(i, j)
                cnt+=1
            if cnt>=2:
                print(answer)
                quit()

더 줄일 수 있는 방법을 생각해보다가, 빙산이 녹을 양을 저장하는 리스트를 따로 만든 후, BFS 함수 내에서 빙산의 개수를 셈과 동시에 녹을 양을 구하여 저장하도록 하고, 저장된 녹을 양을 바탕으로 빙산을 녹이는 방법으로 접근해보았다. 결과는 성공적이었다.

• n, m을 입력받는다.
• 빙산의 정보를 담을 리스트 ocean을 선언한다.
• n번 반복하는 for문을 통해 ocean을 입력받는다.
• 동서남북 방향을 dy, dx에 저장한다.
• bfs함수를 s_y, s_x를 인자로 갖도록 선언한다.
  -> chk[s_y][s_x]를 True로 갱신한다.
  -> q를 deque로 선언한다.
  -> q에 (s_y, s_x)를 넣는다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> q에서 y, x를 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny를 y+dy[i]로 저장한다.
  ---> nx를 x+dx[i]로 저장한다.
  ---> 만약 ny가 0이상, n미만이고, nx가 0이상, m미만일 경우,
  ----> 만약 ocean[ny][nx]가 0보다 크고 chk[ny][nx]가 False일 경우,
  -----> chk[ny][nx]를 True로 갱신한다.
  -----> q에 (ny, nx)를 넣는다.
  ----> 만약 ocean[ny][nx]가 0과 같을 경우,
  -----> cnt[y][x]를 1 증가시킨다.
• 정답을 저장할 변수 answer를 0으로 선언한다.
• 무한 반복하는 while문을 돌린다.
  -> 방문 처리에 사용할 리스트 chk를 n*m으로 선언하고, False로 채운다.
  -> 빙산의 감소량을 저장할 리스트 cnt를 n*m으로 선언하고, 0으로 채운다.
  -> 섬의 개수를 카운팅할 변수 island를 0으로 선언한다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> m번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 ocean[i][j]가 0보다 크고, chk[i][j]가 False일 경우,
  ----> bfs(i, j)를 호출한다.
  ----> island를 1 증가시킨다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> m번 반복하는 j에 대한 for문을 돌린다.
  ---> ocean[i][j]에서 cnt[i][j]를 뺀다.
  ---> 만약 ocean[i][j]가 0보다 작을 경우,
  ----> ocean[i][j]를 0으로 갱신한다.
  -> 만약 island가 0일 경우,
  --> 0을 출력하고 while문을 탈출한다.
  -> 만약 island가 2 이상일 경우,
  --> answer를 출력하고 while문을 탈출한다.
  -> answer를 1 증가시킨다.

Code

import sys
from collections import deque
input=sys.stdin.readline
n, m=map(int, input().split())
ocean=[]
for _ in range(n):
    ocean.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
def bfs(s_y, s_x):
    chk[s_y][s_x]=True
    q=deque()
    q.append((s_y, s_x))
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<n and 0<=nx<m:
                if ocean[ny][nx]>0 and not chk[ny][nx]:
                    chk[ny][nx]=True
                    q.append((ny, nx))
                elif ocean[ny][nx]==0:
                    cnt[y][x]+=1
answer=0
while True:
    chk=[[False]*m for _ in range(n)]
    cnt=[[0]*m for _ in range(n)]
    island=0
    for i in range(n):
        for j in range(m):
            if ocean[i][j]>0 and not chk[i][j]:
                bfs(i, j)
                island+=1
    for i in range(n):
        for j in range(m):
            ocean[i][j]-=cnt[i][j]
            if ocean[i][j]<0:
                ocean[i][j]=0
    if island==0:
        print(0)
        break
    if island>=2:
        print(answer)
        break
    answer+=1