Python : 빙산

문제

문제가 길어서 링크로 대체

풀이

• 그래프 탐색, BFS로 푼 문제

• 크게 두가지 과정이 있다.
  1. 녹인다.
  2. 덩어리 수를 확인한다.

• 녹일 때는 순차적으로 녹이면 이전에 녹아버린 빙산 좌표 값이 0이 되버리면서 틀리게 되므로
  deepcopy()를 사용하여 배열을 깊은 복사 하고 그걸 깎은 뒤 원래 배열에 추가해주었다.

  		ices_clone = deepcopy(ices) # 복사
  		... melting 작업 ...
     		ices = ices_clone  # 깎은 뒤 넣어주기

• 그 다음에는 BFS로 슥슥 돌면서 방문한 좌표 False -> True 로 바꿔 주면

  방문 안한 곳 = 새로운 덩어리

이므로 카운팅해준뒤 2 이상이면 출력한다.

잡담

• 작년 말 롯데 인턴 선발 시험에서 나왔던 문제와 동일하다.
• 그땐 뭔가 어려웠고 지금도 골4에 정답률 25%라 어렵겠다 했는데 생각보다 금방 풀었다.
• Python3은 시간초과라서 Pypy3로 했는데 시험에서는 pypy3을 제공하진 않으니까 이 코드는 못 쓸거 같다. .
• 문제 출처가 KOI라지만 초등부 대상인 문제라서 좀 충격받았다.

전체 코드

import sys
from copy import deepcopy

r = sys.stdin.readline

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def melt(x, y):
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < n and 0 <= ny < m:
            if ices[nx][ny] == 0 and ices_clone[x][y] > 0:
                ices_clone[x][y] -= 1


def bfs(x, y):
    queue = [(x, y)]

    while len(queue) != 0:
        cur_x, cur_y = queue.pop(0)
        for k in range(4):
            nx = cur_x + dx[k]
            ny = cur_y + dy[k]

            if 0 <= nx < n and 0 <= ny < m:
                if ices[nx][ny] != 0 and ch[nx][ny] == False:
                    ch[nx][ny] = True
                    queue.append((nx, ny))


if __name__ == '__main__':
    n, m = map(int, r().split())
    ices = [list(map(int, r().split())) for _ in range(n)]

    day = 0

    while True:
        day += 1
        count = 0
        ch = [[False] * m for _ in range(n)]
        ices_clone = deepcopy(ices)

        for i in range(n):
            for j in range(m):
                if ices[i][j] != 0:
                    melt(i, j)

        ices = ices_clone

        for i in range(n):
            for j in range(m):
                if ices[i][j] != 0 and not ch[i][j]:
                    count += 1
                    ch[i][j] = True
                    bfs(i, j)

        if count == 0:
            day = 0
            break
        elif count >= 2:
            break

    print(day)