1/8 Coding Test

✅ Coding Test

🎈 2573 빙산

2차원 배열로 현재 빙산의 높이가 2차원 배열로 표시되는데, 빙산 이외의 바다에 해당되는 칸은 0으로 제공된다.

빙산의 높이는 바닷물에 많이 접할수록 더 빨리 줄어들기 때문에 1년 뒤 빙산의 높이는 현재 빙산의 높이에서 바닷물에 접해있는 면의 수 만큼 감소한다.

한 덩어리의 빙산이 주어질 때 해당 빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하는 프로그램을 작성하는 문제로, 만일 전부 녹을 때까지 두 덩어리 이상으로 분리되지 않는 경우 0을 출력한다.

입력갑으로 두 정수 n, m (행/열) 이 주어지고 n줄만큼 배열의 각 행을 나타내는 정수가 m개씩 주어질 때 빙산이 분리되는 최초의 시간을 출력하는 문제.

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(r, c , sea, visited):
    queue = deque([[r, c]])
    visited[r][c] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                # 다음으로 이동할 위치가 바다인 경우
                if graph[nx][ny] == 0:
                    sea[x][y] += 1
                else:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
    return True

# 년도 변수 answer로 지정
answer = 0

while True:
    # 1번 탐색 시 1년 소요. (빙산 방문여부, 주변 바다 개수 갱신 필요)
    visited = [[False]*m for _ in range(n)]
    sea = [[0]*m for _ in range(n)]
    # 빙산 개수
    iceberg = []
    for i in range(n):
        for j in range(m):
            # 다음 위치가 빙산이고 방문한 적 없다면 bfs 탐색 진행, 빙산이 두개 이상이 되면 [True, True]가 됌.
            if not visited[i][j] and graph[i][j] != 0:
                iceberg.append(bfs(i, j, sea, visited))
    # 빙산 매년 녹이기
    for i in range(n):
        for j in range(m):
            graph[i][j] -= sea[i][j]
            if graph[i][j] <= 0:
                graph[i][j] = 0
    # 빙산 분리 안되거나 2개 이상이면 중단
    if len(iceberg) >= 2 or len(iceberg) == 0:
        break
    answer += 1

# while 반복문에서 iceberg가 2개 이상이라 중단된 경우를 대비, 아닌 경우는 분리가 안된 케이스 말곤 없음
if len(iceberg) >= 2:
    print(answer)
else:
    print(0)

< 코드 해설 >

구현 자체에 있어 오래 걸린 문제.

• 핵심은 매년 빙산의 높이가 바닷물에 접해있는 면의 수만큼 감소한다는 것이다.

아이디어와 구현한 부분은 다음과 같다.

1. 주어진 입력값 (가로, 세로, 그래프)과 주변 빙산/바다 여부를 위해 dx/dy 생성
2. 현재 위치의 행, 열, 주변 4면 중 바다 여부(2차원 배열), 빙산 방문 여부를 변수로 두고 기본적인 bfs문을 활용. 핵심은 현재 위치가 빙산일 때에만 BFS를 탐색하되 주어진 범위 내 다음 이동할 위치가 빙산인지, 바다인지를 따져가면서 값을 갱신시켜준다.
3. 빙산이 모두 녹을 때까지 진행을 위해 while loop 활용
4. 매년 빙산 방문여부, 주변 바다확인을 해야 하기에 2차원 배열 2개를 저장하고 빙산이 2개 이상이 되는지 여부를 iceberg 빈 리스트에 bfs결과를 넣어준다.
5. 주석으로도 달아놓았지만 다음 이동할 위치가 빙산이고 방문한 적이 없다면 bfs 탐색을 진행해 iceberg의 True 결과를 저장한다. (만일 빙산이 분리된다면 [True, True, True] 형태로 저장될 것이다.
6. 빙산을 매년 녹여주기 위해 bfs 탐색 이후 graph - sea를 진행한다.
7. 결과적으로 iceberg 배열 내 길이가 0이면 아직 분리가 되지 않은 것이고, 2이상이라면 분리가 된 것이기에 중단해주고 년도를 제일 마지막에 갱신한다
8. while문을 나올 때 iceberg가 2이상이라 중단된 경우엔 지금까지 갱신된 년도를, 반대의 경우는 분리되지 않은 케이스이므로 0만 출력!