11달 전의 내가 C로 풀었길래 오늘날의 나도 엄청 쉽게 풀 수 있을 줄 알고 겁없이 덤볐다가 시간 초과, 메모리 초과, 런타임 에러, 틀렸습니다 4종 세트로 아주 피멍 들도록 쌔려맞았다. ㅠ
그래도 결국은 해냈다.
💡 그럼 이제 정리를 해보자.
일단 처음에 한 생각은
1. DFS나 BFS로 맵 한바퀴 쭉 돌면서 녹일 숫자를 저장하는 맵을 만들자.
2. 이중포문 돌면서 (빙산 - 녹일 숫자)
3. DFS나 BFS로 빙산 갯수 확인해주자.
이렇게 간단한 문제일줄 알았는데.. 구현해보니 매년 1~3을 반복해야해서 while문 안에 1~3이 들어가야 한다.
그럼 while문 안에 이중포문이 3개가 들어가면서 시간, 메모리에 취약한 파이썬씨는 시간 초과를 뱉게 된다.
그렇다고 파이파이는 되는가? 메모리에 취약한 파이파이씨는 얄짤없이 메모리 초과를 뱉게 된다. 살려주세요 ....
아무튼 그래서 로직을 수정해야하는데 ..
💡 내가 시간을 줄이기 위해 노력한 부분들
-
이중포문으로 전체를 탐색하면서 바다와 인접한 부분을 구하고 그걸 다시 맵에 담으면 느리다.
-> 입력받을 때, 빙산이 있는 좌표만 큐에 저장해둔다. 그러면 탐색할 때, 이중포문으로(0,0) ~ (n-1, m-1)을 전부 돌면서 탐색하는 것에 비해 효율적이다. -
문제를 잘 읽자!!
-> 첫번째 행, 열과 마지막 행, 열은 무조건 0으로 채워진다는 것을 읽지 않아서 엉뚱한 반례로 한참을 고생했다. 문제를 잘 읽자!
그리고 이 조건덕분에 for문 범위를(0, n)이 아니라(1, n-1)로 줄여줄 수 있다. 매우 작지만 우리 연약한 파이썬, 파이파이씨에게 조금이라도 힘을 주고 싶다. -
빙산을 녹일 만큼을 저장한 행렬
minus를iceberg에서 빼줄 때, 1번과 같이 빙산이 있는 부분만 탐색을 했다면 훨씬 빠르다. 또한 빼주고 나서도 빙산의 높이가 0보다 크면, 그 좌표를 또 큐에 저장해줘서 다음 해를 지날 때 이용한다. -
가장 중요한 점!! 갯수를 세는 bfs는 모든 갯수를 다 셀 때까지 돌 필요가 없다.
-> 1~3번을 해주고도 시간초과 등 피멍 4종세트로 한참을 맞았다. 28일 밤부터 29일 점심까지 맞았으니까 거의 12시간정도 맞은 셈이다. 내가 제출한 빙산이 두 페이지다.
그렇게 한참을 고생하다가 주변의 도움을 받아, 녹이고 난 뒤 빙산 갯수 세는 bfs를 빙산 갯수 다 셀 때까지 돌 필요가 없다는 것을 알게 됐다. 처음 들으면 이해가 좀 어려운데, 녹이기 전에 빙산인 곳의 갯수와 녹이고 난 후에 한 덩이에서의(bfs 한번) 빙산의 갯수가 다르면 빙산이 쪼개졌다고 생각할 수 있다.
그러면 bfs를 여러 번 돌 필요 없고, 1번만 돌고 확인하고 바로 break를 하던, 다음 해로 넘어가던 할 수 있다.
이때, 녹이고 나서 이중포문을 돌면서 bfs 시작점을 잡아줘야 한다. 처음에start_x,start_y를 0으로 초기화해두고 빙산이 있으며, 아직 방문안한 곳을 시작점으로 잡아준다. 만약 둘다 그대로 0이라면 빙산이 없는 것이므로 0을 출력하면 된다. 반복문의 마지막에서 두 값을 다시 초기화해줘야 다음 해에도 쓸 수 있다.
만만하게 생각하고 덤볐다고 정말 많이 고생한 문제라서 블로그에 적어둔다.
문제를 풀면서 구글링을 많이 하는데, 보통 블로그에는 코드만 있거나 아주 간단한 설명만 있어서 이해가 힘들었다. 그래서 나는 앞으로 내가 어떻게 생각했는지, 어떻게 개선했는지 등 문제 풀면서 한 생각들을 의식의 흐름대로 정리해보려 한다.
💡 코드
import sys
from collections import deque
read = sys.stdin.readline
n, m = map(int, read().split())
iceberg = []
q = deque()
for i in range(n):
iceberg.append(list(map(int, read().split())))
for j in range(1, m-1):
if iceberg[i][j]:
q.append((i, j))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 녹일 만큼 덱에 저장
def melt():
minus = deque()
while q:
x, y = q.popleft()
cnt = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if iceberg[nx][ny] == 0: cnt += 1
minus.append((x, y, cnt))
while minus:
x, y, cnt = minus.popleft()
if cnt:
iceberg[x][y] -= cnt
if iceberg[x][y] > 0: q.append((x, y))
elif iceberg[x][y] < 0: iceberg[x][y] = 0
else:
if iceberg[x][y] > 0: q.append((x, y))
return len(q)
# 방문처리, 빙산인 칸의 개수 세주기
def bfs(x, y):
ice = deque()
ice.append((x, y))
visited[x][y] = True
count = 1
while ice:
x, y = ice.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (0 < nx < n-1 and 0 < ny < m-1) and iceberg[nx][ny] and not visited[nx][ny]:
ice.append((nx, ny))
visited[nx][ny] = True
count += 1
return count
year = 0
while True:
component = 0
year += 1
visited = [[0 for _ in range(m)] for _ in range(n)]
ice_size = melt()
# 한 해 지나고 빙산 수 세기
# bfs 한 번 돌려서 빙산인 칸의 수를 확인하는데 큐에 남아있고 전년도와 다르면 빙산이 갈라진거니까 그때 출력하면 됨
# -> bfs 여러번 돌릴 필요 없음
for i in range(1, n-1):
for j in range(1, m-1):
if iceberg[i][j] and not visited[i][j]:
start_x, start_y = i, j # bfs 시작점 찾기
# 녹인 빙산의 크기
if start_x and start_y:
one_bfs_size = bfs(start_x, start_y)
if ice_size != one_bfs_size: # 빙산이 갈라졌어요
print(year)
break
else:
print(0)
break
start_x, start_y = 0, 0
