[백준 10711번] 모래성(파이썬)

https://www.acmicpc.net/problem/10711

10711번: 모래성

이 문제는 구글링하면서

허탈했던 문제.

아니...뭐야...이렇게 쉬웠다고?

 

하지만 정작 문제를 처음 접할때는

많이 낑낑댔습니다.

체감상 어렵게 느껴진 부분은

8방향의 좌표를 다 보고 

모래성을 무너트리는 것.

H와 W의 범위값이

최대 1000이라고 되어있으니

첫,마지막 행과 열을 제외하더라도

최대 999x999x8의 경우를 계산해야합니다.

모래성이 없는 경우는 스킵하더라도

엄청난 계산량이 요구가 됩니다.

딱 봐도 시간초과가 뜨기 쉽상.

 

그런데 문제 알고리즘이

'너비 우선 탐색'이라길래

더 황당했습니다.

BFS라고요?

이게 어째서죠?

어떻게 BFS를 쓰지??

 

그러다 구글링해보니

왜 BFS인지 알게되었습니다.

관점을 전환해보면 이해가 됩니다.

비어이는 것 기준으로

파도가 몇번을 칠 때

모래성이 없어지는 지 계산하면 어떨까요?

이런 식으로 계속 모래를 쓰러트리는 식으로 나아간다면

몇 번 파도가 쳐야지 

모래성이 수렴하는지 구할 수 있습니다.

#백준 10711번 모래성
from collections import deque
H,W=map(int,input().split())
tmp=[list(input().rstrip())for _ in range(H)]
room=[[0]*W for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
q=deque()
for x in range(H):
    for y in range(W):
        if tmp[x][y]=='.':
            q.append([x,y])
            visited[x][y]=0
            continue
        room[x][y]=int(tmp[x][y])


dir=[(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]
answer=0
while q:
    x,y=q.popleft()
    for d in range(8):
        nx=x+dir[d][0]
        ny=y+dir[d][1]

        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue

        if visited[nx][ny]>=0:
            continue
        #파도로 무너트리기
        if room[nx][ny]>0:
            room[nx][ny]-=1
        #모래가 없는 지역이라면
        #이전의 모래가 없는 구역기준으로 파도하나가 더 필요하다
        if room[nx][ny]==0:
            visited[nx][ny]=visited[x][y]+1
            answer=max(answer,visited[nx][ny])
            q.append([nx,ny])

print(answer)

 

구현자체는 정말 쉬웠지만

아이디어를 떠올리는 게 무척이나 어려웠던 문제입니다.

문제 자체를 기억해두어서

유사한 문제가 나올 때 써먹어야겠네요.