[백준] 10711 모래성(Python) - BFS

📌 문제

명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 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.
......

예제 출력1

3

---

예제 입력2

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

예제 출력2

35

---

📌 풀이

Code

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

def BFS():
    queue = deque()      # 빈 큐 만들기
    
    # '.'인 칸 좌표를 큐에 넣기 / '.'는 모두 0으로 바꾸기 / 숫자 칸 데이터 타입 int로 바꾸기
    for r in range(H):
        for c in range(W):
            if grid[r][c] == '.':
                queue.append([r, c, 0])
                grid[r][c] = 0
            else:
                grid[r][c] = int(grid[r][c])
    
    while queue:
        # 큐에서 '.' 좌표, 파도 횟수 정보 빼내기
        r, c, wave = queue.popleft()
        # '.' 주변 8방향 탐색   
        for k in range(8):
            nr = r + dr[k]
            nc = c + dc[k]
            # '.' 주변에 있는 숫자들 모두 1 감소시키기
            if 0 <= nr < H and 0 <= nc < W and grid[nr][nc]:
                grid[nr][nc] -= 1
                # 모래성이 무너졌으면
                if grid[nr][nc] == 0:
                    # 무너진 부분 좌표, 파도횟수+1 정보를 큐에 넣기
                    queue.append([nr, nc, wave+1])    

    return wave


H, W = map(int, input().split())                # 격자 가로 세로 크기
grid = [list(input()) for _ in range(H)]        # 격자
dr = [0, 0, 1, -1, 1, 1, -1, -1]                # 행 델타
dc = [1, -1, 0, 0, -1, 1, -1, 1]                # 열 델타

# BFS 함수 호출하고, 리턴 값인 파도 횟수 출력            
print(BFS())

---

Solution

1. 격자 가로 세로 크기와 격자 판을 입력 받고, 8방향 델타 값 리스트 만들기

 

2. 빈 큐를 생성하고, '.'인 칸 좌표를 모두 큐에 넣기

(너비 탐색을 한 사이클 진행할 때마다 파도 친 횟수를 1씩 늘리기 위해 wave=0 값도 함께 넣기)

• '.'를 모두 0으로 바꾸기 
• 모든 숫자 칸 데이터 타입을 int로 바꾸기

3. BFS 수행

1. 큐에서 '.' 좌표와 파도 횟수 정보 큐에서 빼내기
2. 해당 '.' 좌표의 주변 8방향 탐색
3. 주변에 숫자가 있다면 1 감소시키기
4. 감소된 숫자가 0이되면, 0이된 칸 좌표와 파도 횟수에 +1한 값을 큐에 넣기
5. 큐가 비어있을 때까지 1~4 과정 반복

주변에 숫자가 있다면 1 감소 시키기

 

4. 최종 파도 횟수 반환

---

깨달은 점

저는 처음에 이 문제를 BFS가 아닌 단순 구현으로 접근했었습니다.

아래와 같이 그냥 모든 격자를 순회하며 숫자를 만나면 8방향을 탐색하는 방식으로 말이죠.

import sys
input = sys.stdin.readline

H, W = map(int, input().split())                # 격자 가로 세로 크기
grid = [list(input()) for _ in range(H)]        # 격자
dr = [0, 0, 1, -1, 1, 1, -1, -1]                # 행 델타
dc = [1, -1, 0, 0, -1, 1, -1, 1]                # 열 델타

wave_num = 0      # 파도 횟수

while True:
    destroyed = []                            # 파괴되는 블럭 좌표 리스트
    for r in range(H):
        for c in range(W):
            if grid[r][c] != '.':             # 숫자면
                cnt = 0                       # 카운트 초기화
                # 8방향에 있는 '.' 개수만큼 카운트 올리기
                for k in range(8):
                    nr = r + dr[k]
                    nc = c + dc[k]
                    # 그리드 범위 안이고, '.'이면 카운트 증가
                    if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == '.':
                        cnt += 1
                # 카운트가 현재 위치 튼튼함 정도보다 크거나 같으면 리스트에 저장         
                if cnt >= int(grid[r][c]):         
                    destroyed.append([r, c])
    
    # 모래성에 변화가 없었으면 반복 종료
    if not destroyed:
        break
    
    # 리스트에 저장된 모든 파괴할 블록을 '.'으로 바꾸기
    while destroyed:
        row, col = destroyed.pop()
        grid[row][col] = '.'
    
    wave_num += 1      # 파도 한번 쳤음

print(wave_num)

 

그랬더니 그 결과는...?!

 

시.간.초.과 ㅠㅠ 당연한 결과지요...

 

저도 처음에 숫자 칸이 아닌 '.' 칸 주변을 탐색하며 숫자를 1씩 낮추는 방식을 생각하지 않았던 건 아니지만..
숫자를 낮추게 되면 한번 파도가 지나가고 난 뒤 다시 원래 숫자로 돌려놔야 한다고 생각해서 포기했었습니다.

 

 그런데!!!

그럴 필요가 없었습니다..!

제일 처음에 모래가 없는 부분 좌표들이 주변 숫자에 -1을 수행하며 한번 휩쓸고 간 뒤에는 더이상 영향을 주지 않기 때문이죠! (큐에서 이미 빠진 상황이기 때문)
즉, 처음에 '.' 부분은 딱 한번만 숫자들에 영향을 주고, 그 이후에 영향을 받아 무너진 모래성 칸만이 추가적으로 주변 모래성에 영향을 주게 됩니다.

 

이번 문제는 극한의 BFS 이해도를 요구하는 문제였네요....

전 아직 한참 부족하네요 ㅜㅜ

 

앞으로 이런 문제를 잘 풀기 위해서는 BFS를 언제 사용해야할지 감을 잡는게 중요할 것 같아요.

그런 감은 많이 풀어봐야 생기겠죠..!

 

어느 때에 BFS를 써야하는지 확실하게 감각이 생기는 그 날까지 열심히 달려보겠습니다!!