[BOJ][🟡2][백준#10711] 모래성

문제 출처

BAEKJOON Online Judge #10711

문제

명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 산화하려는 것으로 보인다. 이런 완벽에 가까운 물품인 모래를 두고서 해수욕이나 헤엄을 치는 것은 인생을 낭비하는 것과 같다고 생각한다. 하지만 아무도 명우의 말에 공감해주지 못했고, 결국 명우는 혼자서 모래성을 만들었다. 다른 친구들이 혼신의 힘을 다해 놀고있을 때 명우는 혼신의 힘을 다해 모래성을 쌓았다. 이 모래성은 언젠간 파도에 의해서 무너질 터… 명우는 이런 무너짐도 예술의 일환으로 이해한 사람이므로 무너지는 것도 고려해서 모래성을 만들었다. 그가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다. 이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명이 궁금해졌다. 모래성은 위에 서술한 바와 같이 파도가 한번 칠 때마다 특정 부분이 무너저내리는 방식으로 모양이 변화된다. 모래성이 더이상 모양이 변하지 않게 되려면 (모양이 수렴되려면) 파도가 몇번 쳐야하는지 구해보자.

입력

첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 ‘.’ 이다. 1~9는 그 격자의 모래의 강도를 나타내며, ‘.’는 모래가 없다는 뜻이다. 모래성은 격자의 가장자리와 접해 있지 않다.

출력

몇번의 파도가 몰려오고나서야 모래성의 상태가 수렴하는지를 구한다.

예제

예제 1

입력

5 6
......
.939..
.3428.
.9393.
......

출력

3

예제 2

입력

10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........

출력

35

My Sol

I, J = map(int, input().split())
mat = [list(map(lambda x: (x if x=='.' else int(x)), input())) for _ in range(I)]
cass = [[[0xfff, 0] for _ in range(J)] for _ in range(I)]

# 최초 높이 계산
Q = set()
ql = 0
for i in range(I):
    for j in range(J):
        if mat[i][j]!='.':
            cass[i][j][0] = int(mat[i][j])
            Q.add((i, j))
            ql += 1


# 모두 모래라면 0 출력
if not Q:
    print(0)
    quit()

# 최초 removeSet 확인
removeSet = set()
while Q:
    ni, nj = Q.pop()
    cnt = 0
    for di in range(-1, 2):
        for dj in range(-1, 2):
            si, sj = ni+di, nj+dj
            if mat[si][sj]=='.':
                cnt += 1

    cass[ni][nj][1] = cnt
    if cnt >= cass[ni][nj][0]:
        removeSet.add((ni, nj))

wave = 0
while removeSet:
    removeSet2 = removeSet
    removeSet = set()
    while removeSet2:
        ni, nj = removeSet2.pop()
        mat[ni][nj] = '.'

        for di in range(-1, 2):
            for dj in range(-1, 2):
                si, sj = ni+di, nj+dj
                if mat[si][sj]=='.': continue
                cass[si][sj][1] += 1

                if cass[si][sj][0] == cass[si][sj][1]:

                    removeSet.add((si, sj))

    wave += 1

print(wave)

BFS를 극한으로 사용하는 문제였다. 반복되는 코드가 일부 있는데, 경우를 나누기 위해서 불가피했다. 배열의 크기가 크기 때문에 점이 아닌 숫자가 있는 좌표에 대해 해당 좌표의 값과, 주변의 점의 개수를 세었고, 이 주변의 점의 개수가 처음에 좌표의 값보다 크거나 같으면 다음 파도에서 제거 대상이므로 removeSet에 좌표를 넣어준다. 만약 처음에 모든 좌표에 대해 탐색했는데, 값이 모두 ., 즉 모래성이 없다면 0을 출력하도록 초기 설정하였고, 모래성이 있더라도 변하지 않는다면 removeSet이 빈 set이 되므로 while을 통과하지 않고 바로 wave 0을 출력하게 된다.

while 문의 반복은, 이전 파도에서 어떻게든 부서지는 모래성이 있는 경우 실행되는데, 해당 제거 대상의 좌표를 .으로 처리하고, 팔방의 탐색 좌표에 대해 탐색 좌표가 .이라면 continue한다. 만약 제거 대상의 주변 팔방에 모래성이 있다면, 해당 모래성에게도 주변의 모래성이 하나 제거되는 것이므로, 이를 값을 1 추가해준다. 생각해보니 값을 하나씩 줄여가면 어땠을까 싶다. 메모리를 낭비하게 되었지만 어쨋든 기능은 한다.

그동안 반복 내의 cass는 성의 견고함이 항상 주변의 모래 개수보다 많은데, 제거 대상의 모래성이 삭제되면서 모래양이 늘어서 성의 견고함과 같게 된다면, 해당 탐색좌표를 removeSet에 추가하고 다음 wave 때 제거하는 방식으로 사용한다. 이렇게 removeSet이 채워지지 않는, 즉 wave에도 제거 대상이 없다면 wave를 출력하면 되겠다.

결과

맞았습니다!!

모범답안

출처

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

dydx = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]

H, W = map(int, input().split())
board = []
q = deque()
for i in range(H):
    board.append(list(input().rstrip()))
    for j in range(W):
        if board[i][j] == ".":
            q.append((0, i, j))
            board[i][j] = 0
        else:
            board[i][j] = int(board[i][j])

while q:
    t, y, x = q.popleft()
    for dy, dx in dydx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W:
            board[ny][nx] -= 1
            if board[ny][nx] == 0:
                q.append((t+1, ny, nx))
print(t)

채점 현황에서 시간적으로나, 메모리적으로 효율적인 코드를 찾아 분석한다. set 대신 q를 사용하다. 중복 좌표가 없기 때문에 deque인 q를 사용해도 괜찮을 것이다. 위에서 코드 리뷰를 하면서 느꼈던 값을 내리는 건 어떨까 싶었는데, 딱 그 코드를 작성하였다. 그리고 sys.stdin.readline을 나도 사용했다가 ValueError 발생으로 지워주었는데, 이 분은 사용이 됐나보다. 배열의 크기가 크므로, 이 역시 영향을 주었을 것이다.

나는 wave로 아예 카운트를 했는데, 이 분은 좌표에 대해서 카운트를 t에 넣어주었다. 이렇게 모든 q의 요소에 대해 t가 매번 갱신되다가 q가 바닥나면 마지막 q 요소의 t가 최대로 파도가 친 횟수이므로, 이를 출력하는 것이다. 상당히 잘 짠 코드인 것 같다.