지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일 년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일 년 후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
굉장히 오랜 시간 공들여 푼 문제.... 파이썬으로 하니까 메모리 초과랑 시간 초과의 2연타를 정신없이 맞았다.....
이 문제는 BFS를 이용하여 풀었는데, 방법은 다음과 같다. (DFS를 사용해도 된다.)
0이 아닌 인덱스가 나왔을 시(아직 방문하지 않은) bfs탐색을 진행한다.
bfs 탐색이 진행된 총 횟수가 빙하의 개수가 될 것이다.
빙하의 네 면적 중 0의 갯수만큼 빙하를 녹인다. (주의)
빙하의 덩어리가 0이거나 2이상일 경우 종료.
주의해야 할 점은 bfs를 할 때 큐에 인덱스를 넣을 때 넣는 순간 방문을 했다는 표시를 함으로써 중복 탐색을 방지해야 한다. 그렇지 않으면 얄짤없이 시간 초과에 걸린다. (필자는 이 부분을 몰라서 하루 종일 헤맸다.)
또 한가지 주의사항은 빙하를 녹이는 과정에 있다.
빙하를 녹일 때 현재 상태를 기준으로 녹여야 한다는 것이다.
파란 부분을 녹이려고 할 때 상하좌우를 탐색해서 0인 곳이 2개이므로 높이가 2 낮아지게 된다. 그렇게 된다면 0이 되어 아예 없어지게 된다.
문제는 그 다음이다. 빨간 부분을 녹여야 하는데, 원래 파란 부분이었던 곳이 녹아 없어지면서 0의 부분이 한 군데 더 늘어났다. 녹아야 할 정도가 2에서 3으로 증가하게 되는 것이다.
그런데 그러면 안된다!! 녹을 때는 현재 상태를 기준으로 녹아야 한다는 것이 이 말이다. 빨간 부분이 1이 돼야 하는 것이 아니라 원래 파란 부분이 있었던 경우에서 녹은 2로 바뀌어야 한다는 것!
빨간 부분의 빙하 파란 부분이 존재했다는 기준으로 녹아 최종적으로 2가 되어야 한다.
이런 주의점을 가지면서 녹여야 한다는 것만 생각하면 된다.
필자는 BFS 탐색을 하면서 빙하를 녹이는 작업도 동시에 진행하였다. 빙하가 녹는 정도의 que를 하나 더 만들어서 그곳에다가 (인덱스, 녹는 정도)를 저장하고 탐색이 다 끝나면 que의 값을 하나씩 빼서 녹이는 형식으로 짰다.
import sys
from collections import deque
def bfs(i,j,visit) :
que = deque([[i,j]])
melting_que = deque() # 빙하가 녹는 위치와 녹는 정도를 저장하는 큐
visit[i][j] = 1
while que :
i,j = que.popleft()
melt_cnt = 0
for d_x, d_y in direction :
next_x = i + d_x
next_y = j + d_y
if 0 <= next_x <= x-1 and 0 <= next_y <= y-1 and visit[next_x][next_y] == 0:
# 빙산의 높이가 있고 방문을 안했을 경우 que에 값 넣어주기
if glacier[next_x][next_y] != 0:
visit[next_x][next_y] = 1 # 방문 체크
que.append([next_x,next_y])
# 사방향 탐색 시 0일 경우 melt_cnt 증가
else :
melt_cnt += 1
if melt_cnt :
melting_que.append([i,j,melt_cnt])
return melting_que
input=sys.stdin.readline
year = 0 # 몇 년이 지났는지 판단하는 변수
x, y = map(int,input().split())
glacier = [[int(n) for n in input().split()] for _ in range(x)]
direction = ((1,0),(-1,0),(0,-1),(0,1)) #동서남북
#반복문 종료 조건 -> 빙산의 갯수가 0이거나 2일 경우
while True :
cnt = 0 # 빙산의 갯수를 담는 cnt 변수
visit = [[0 for _ in range(y)] for _ in range(x)] # bfs를 위한 탐색 확인 리스트
for i in range(x-1) :
for j in range(y-1) :
if glacier[i][j] != 0 and visit[i][j] == 0 : #빙하의 높이가 남아있고 방문하지 않을 경우
cnt += 1 # 빙산의 갯수 추가
melt = bfs(i,j,visit) # bfs 시작을 하고 각 좌표별로 녹는 정도 반환
while melt :
m_x, m_y, m = melt.popleft()
glacier[m_x][m_y] = max(glacier[m_x][m_y]-m, 0)
if cnt == 0 :
year = 0
break
if cnt >= 2 :
break
year += 1 # 일 년 증가
# 빙산의 갯수가 0이거나 2일 경우 반복문 종료
print(year)
코드가 조금 복잡해 보일 수도 있으나 주석과 같이 천천히 읽어보면 어떤 느낌인지 감이 올 것이다.
추가로 마지막 행과 마지막 열은 무조건 0이 들어가기 때문에 탐색 조건에 포함시키지 않았다. (이것도 시간 줄이기 위한 몸부림...) pypy3로 제출하니 맞았다고 떴다!!!!
전체적인 흐름을 잡고 알고리즘을 짜다가 자잘한 부분에서 엄청나게 애를 먹은 문제였다. 덕분에 문제를 제출하면서도 시간 초과에 걸릴까 봐 계속 조마조마했던 시간이지 않았나 싶다.
