문제
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
2 4 5 3
3 2 5 2
7 6 2 4 그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
2 4 1
1 1 5
5 4 1 2 그림 2
3
4
3 2 그림 3
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
예제 입력 1
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0예제 출력 1
2최종 코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(N)]
def bfs(start_x, start_y, visited):
queue = deque([(start_x, start_y)])
visited[start_x][start_y] = True
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and iceberg[nx][ny] > 0:
visited[nx][ny] = True
queue.append((nx, ny))
def count_chunks():
visited = [[False]*M for _ in range(N)]
chunks = 0
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0 and not visited[i][j]:
bfs(i, j, visited) # 변경된 부분
chunks += 1
return chunks
def melt_ice():
melting = [[0]*M for _ in range(N)]
directions = [(-1,0), (1,0), (0,-1), (0,1)]
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0:
melt_amount = 0
for dx, dy in directions:
nx, ny = i + dx, j + dy
if 0 <= nx < N and 0 <= ny < M and iceberg[nx][ny] == 0:
melt_amount += 1
melting[i][j] = min(iceberg[i][j], melt_amount)
for i in range(N):
for j in range(M):
iceberg[i][j] -= melting[i][j]
years = 0
while True:
chunks = count_chunks()
if chunks >= 2:
print(years)
break
melt_ice()
years += 1
if all(iceberg[i][j] == 0 for i in range(N) for j in range(M)):
print(0)
break
풀이 과정
# 2차원 배열에 빙산의 높이 정보
# 바다는 0 저장(빈칸)
# 0 기준 상하좌우 -1 시켜줌
# 0까지만 됨 -는 안됨
# 한덩어리가 2덩어리 이상 분리되는 최초의 년수
# 다 녹아도 두덩이 이상 분리 안되면 0 출력
# =============================
# 행 열 N, M(3~300)
# 각 칸은 0~10
# 첫째열, 마지막 열은 항상 0으로 채워짐
# ============================
# 일단 좌표 값 queue, 방문기록? 필요할려나일단 몇번을 봐도 정말 어렵다 나에게..
벌써 2~3번째 풀어보는데도 풀때마다 새로워 늘 짜릿행
다시 한번 분석해보겠다
from collections import deque
N, M = map(int, input().split())
iceberg = [input().rstrip().split() for _ in range(N)]
N, M은 배열의 행, 열의 int화한 입력 값
iceberg는 한 줄씩 담은 빙산의 높이 리스트, 나중에 int화 시켜야함
directions = [(-1,0),(1,0),(0,-1),(0,1)]
상하좌우 리스트
def bfs(start_x, start_y, visited):
queue = deque([(start_x, start_y)])
visited[start_x][start_y] = True
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and iceberg[nx][ny] > 0:
visited[nx][ny] = True
queue.append((nx, ny))
일단 좌표에 대해 방문했나? 를 위해 visited를 사용함(선언은 상위 함수에서 했음)
그리고 queue에 첫 좌표값 넣어서 상하좌우 이동시키면서
0~N 줄 범위 0~M칸 범위 내에서 아직 방문안했고, 0보다 큰 빙산이 존재할땐, 방문했고, 해당 좌표를 새로운 좌표값으로 만든다.
여기선 이전에 풀었던 bfs와 다르게 그냥 움직인 체크만해주고 별다른 행동은 취하지 않음
def count_chunks():
visited = [[False] * M for _ in range(N)]
chunks = 0
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0 and not visited[i][j]:
bfs(i, j, visited)
chunks += 1
return chunks
bfs의 상위 함수인 count_chunks 함수에서 빙산 덩어리 수를 세는데,
일단, 0이아닌 빙산이 이어져있다는건 그 빙산은 끊겨있지 않은 1덩어리를 의미하므로,
chunk 0개부터 선언 및 visited를 이중 배열로 false로 넣어놓은 후,
좌표 반복하면서 iceberg의 i,j위치가 0보다 큰(빙산)이고 아직 방문한적이 없다면,
그 위치부터 bfs함수를 실행시키면서 전체 빙산을 체크해준다.
그 작업이 끝나면 거기까지가 1덩어리 이므로, chunks 도 1을 더해준다
그 후 chunks를 반환
def melt_ice():
melting = [[0] * M for _ in range(N)]
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0:
melt_amount = 0
for dx, dy in directions:
nx, ny = i + dx, j + dy
if 0 <= nx < N and 0 <= ny < M and iceberg[nx][ny] == 0:
melt_amount += 1
melting[i][j] = min(iceberg[i][j], melt_amount)
for i in range(N):
for j in range(M):
iceberg[i][j] -= melting[i][j]
빙산의 크기를 세는 2함수였다면, 이젠 1년 지날때마다 빙산을 녹여주는 함수가 필요한데 바로 이 함수다.
일단 0일땐 상하좌우를 녹이므로, 전체를 0으로 이중배열로 melting에 넣어놓고,
N,M 이중 반복문을 실행하면서 만약 iceberg[i][j]가 0보다 큰 즉, 빙산이라면??
melt_amount를 초기값 0으로 선언해준다 -> 녹을 양
그 후 상하좌우 움직여가며
x좌표 y좌표가 0~N/0~M범위 안에 존재하고, iceberg의 해당 xy좌표가 0일때라면??
즉, 원래 i,j의 좌표의 빙산이 0보다 높으므로 빙산일때(if)
상하 좌우 움직여가며 그 중에 빙산의 높이가 0인 즉, 바다가 상하좌우에서 하나라도 있다면??
1의 높이를 녹여내야 하므로, melt_amount에 1만큼 더해준다(녹인 갯수)
그 다음에
melting[i][j] = min(iceberg[i][j], melt_amount)이 부분이 의미하는건,
만약 iceberg[i][j]=1이였을땐, 상하좌우에 바다가 1개만 있다면(0이1개) melt_amount도 1
즉, melting[i][j]는 min(1,1)이므로 1
결국 로직을 돌리면서 해당 i,j좌표는 1만큼 녹였다고 melting에 담아주는 것
근데 원래 빙산이 6이 높이였고 주변에 0이 4개가 있었다면?
min(6,4)이므로 총 녹은 melting의 해당 좌표는 4
즉, 4가 녹였다. 라고 구할 수 있다.
이 로직에선 iceberg에 대해서는 따로 무슨 작업을 진행하진 않고, 녹은 높이만 구할 수 있다.
그 후
for i in range(N):
for j in range(M):
iceberg[i][j] -= melting[i][j]여기에서 전체 녹은 갯수를 iceberg에서 빼주면 되는데,
예를 들어 빙산의 높이가 2인데, 0이 상하좌우4개이면?? -2가 되는거 아닌가 싶지만
어? 그러다 -가 되면 어떻게? 라고 생각할 수 있지만,
melting[i][j] = min(iceberg[i][j], melt_amount) 여기에서
min(2,4) => melting =2가 되므로 무조건 다 녹으면 0이 될 수 밖에 없다
와.. 이게 머리로는 알겠는데 로직을 짜려니까 진짜 컴퓨터는 대단하다 생각이 든다....
몇번을 봐야 드디어 이해될정도였음 ㅠㅠ골드4문제가 머이리 어려워 ㅠㅠ
그 후 1개의 빙산 덩어리가 2개 이상이 되었을때의 몇년 걸렸는지를 구하는 문제이므로
years = 0
while True:
chunks = count_chunks()
if chunks >= 2:
print(years)
break
melt_ice()
years += 1
if all(iceberg[i][j] == 0 for i in range(N) for j in range(M)):
print(0)
break
일단 경과한 년수 0으로 세팅
그리고 참이라면?
덩어리는 chunks에 그 값을 담고
만약 2개 이상으로 쪼개지면 해당 years를 반환시키고,
melt_ice() 함수로 한번 빙산 녹이고 year1년추가하고 while문 통해 계속 반복
True로 놓은 이유는 계속 반복시킬건데 원하는 값이 나오자마자 break시킬 것이기 때문
그러다 만약
if all() 즉 조건이 모두 참일 경우만?? 내부 로직 실행
iceberg가 모든 배열을 순회하면서 전부 0, 다 녹았다면 그땐 0을 출력
.......................
.......................
지린다 진짜 이거 몇번을 풀어도 바로 못풀것같다... 개어렵네 ㅠㅠ
최종의 최종 코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(N)]
directions = [(-1,0), (1,0), (0,-1), (0,1)]
def bfs(start_x, start_y, visited):
queue = deque([(start_x, start_y)])
visited[start_x][start_y] = True
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and iceberg[nx][ny] > 0:
visited[nx][ny] = True
queue.append((nx, ny))
def count_chunks():
visited = [[False]*M for _ in range(N)]
chunks = 0
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0 and not visited[i][j]:
bfs(i, j, visited) # 변경된 부분
chunks += 1
return chunks
def melt_ice():
melting = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
if iceberg[i][j] > 0:
melt_amount = 0
for dx, dy in directions:
nx, ny = i + dx, j + dy
if 0 <= nx < N and 0 <= ny < M and iceberg[nx][ny] == 0:
melt_amount += 1
melting[i][j] = min(iceberg[i][j], melt_amount)
for i in range(N):
for j in range(M):
iceberg[i][j] -= melting[i][j]
years = 0
while True:
chunks = count_chunks()
if chunks >= 2:
print(years)
break
melt_ice()
years += 1
if all(iceberg[i][j] == 0 for i in range(N) for j in range(M)):
print(0)
break
