[백준] 15944번: 성공

🔈 문제

당연한 이야기지만, 성공으로 가는 길이 항상 평탄하지만은 않다. 온갖 장애물이 가득하고, 장애물에 막혀서 주저앉을 수도 있다. 그래서 그 장애물을 폭파하려고 한다.
성공으로 가는 길은 N×M격자 위에 놓여 있다. 성공으로 가려면 맨 왼쪽 위 칸에서 시작하여 장애물이 없는 상하좌우로 인접한 칸을 밟으면서 맨 오른쪽 아래 칸에 도착해야 한다. 한 번의 폭파 작업으로 D×D 격자 내에 있는 모든 장애물을 없앨 수 있다. 하지만 세상에 공짜는 없는 법. 폭파 작업에도 큰 힘이 들기 때문에, 성공으로 가려면 최소 몇 번의 폭파 작업이 필요한지 알고 싶다.

📝입력

첫 번째 줄에 격자의 행의 개수 N, 열의 개수 M, 폭파의 범위 D가 주어진다(D ≤ N, M ≤ 500, 1 ≤ D ≤ 100).
그 다음 N개의 줄에 격자의 각 행을 나타내는 길이 M의 문자열이 주어진다. “.”은 장애물이 없는 칸, “#”은 장애물이 있는 칸이다. 출발 지점과 성공에는 장애물이 없다.

 

📑출력

첫 번째 줄에 폭파 작업의 최소 횟수를 출력한다.

 

🧐 문제 접근

 

N * M 보드에서 (0, 0) 에서 시작하여 (N - 1, M - 1) 까지 도달하기 위해서 최소 몇 번 벽을 폭파해야 하는가? 를 구해야 하는 문제이다. 벽을 폭파할 때는 한 칸만 부술 수 있는게 아니라 D * D 범위를 폭파시킨다.

 

'그래프', '최소', 라는 키워드가 등장하여 데이크스트라인가 하고 그쪽으로 방향을 틀었다.

여느 데이크스트라 알고리즘 처럼 폭파한 횟수를 기준으로 정렬하며 그래프를 탐색하되, 장애물을 만나면 그곳을 폭파해주는 방식을 생각했었다. 처음에는 장애물을 만나면 해당 장애물을 제거하기 위해 D * D 반복 하면서 폭파된 보드를 업데이트 해주었다. 

 

하지만 이렇게 구현한다면 N * M * D^2로 제한 시간 2초 안에 통과하지 못한다. (500 * 500 * 100^2 = 2,500,000,000)

그럼 N * M * D로 해결해야 하는 문제라는 것을 알 수 있다. 

 

📚 문제 풀이

그럼 D * D 반복하지 않으면서 어떻게 폭파를 할 수 있을까. 아이디어는 직접 폭파하지 않고 워프하는 것이다. 

 

N = 9, M = 9, D = 3 일때, 현재 (4, 4)에 위치했있다고 가정하자.

(4, 4)에 위치

 

D = 3이니 한번 폭파하면 아래 그림처럼 D * D 범위에 효과가 있을 것이다. 

 

 

저 위치에서 폭파시켜서 이동할 수 있는 것을 파악해보면 아래 그림과 같다.

 

 

 

정리하자면 아래 주황색 부분으로 칠해져있는 부분은 현재 위치 (4, 4)에서 폭탄 한번 터뜨려서 이동할 수 있는 범위이다. 

 

 

 

 

D * D 돌면서 보드 업데이트 할 필요 없이 현재 위치에서 폭탄 터지고 난 후의 위치로 워프하면 된다!

물론 현재 위치에서 상하좌우로도 탐색을 한다. 

 

주황색 범위 안에 있는 곳은 탐색 못하는거 아닌가? 하는 의문이 들 수 있지만, 폭탄을 떠뜨린 횟수로 정렬해서 탐색하기 때문에 주황색 범위 안이 모두 장애물이 없다면 빠짐없이 탐색하게 되고, 장애물이 있다면, 현재 위치가 아닌 다른 위치에서 언젠가 방문하게 되어있다. 

 

그럼 이제 데이크스트라 알고리즘을 구현하면 될까?

물론 데이크스트라 알고리즘으로도 풀 수 있다! 하지만 좀 더 관찰해보면, 현재 위치에서 상하좌우로 탐색할 때 장애물이 없다면 폭파 카운트 증가 없이 이동 가능하고, D 만큼 워프 뛸 때에는 폭파 카운트 1 증가하면서 이동하는 것을 알 수 있다.

 

(0과 1... 0과 1의 미로가 보여)

 

그렇다 0 - 1 bfs로도 문제를 해결할 수 있다. 상하좌우 탐색할 때에는 큐 왼쪽에 추가해주고, D 워프 뛸 때에는 큐 오른쪽에 추가해주며 탐색하면 더 효율적인 시간 복잡도로 문제가 해결 가능하다.

 

💻 코드

from collections import deque
import sys
input = sys.stdin.readline
 
n,m,d = map(int,input().split())
 
board = [list(input().rstrip()) for _ in range(n)]
 
 
bomb = [[float('inf')] * m for _ in range(n)]
bomb[0][0] = 0
 
queue = deque([(0,0,0)]) # cnt, y, x, board
 
while queue:
    cnt, y, x = queue.popleft()
    if y==n-1 and x==m-1:
        break
    if bomb[y][x] < cnt: continue
 
    # 상하좌우 탐색
    for dy,dx in ((0,-1), (0,1), (1,0), (-1,0)):
        ny,nx = y + dy, x + dx
 
        if ny < 0 or nx < 0 or ny >= n or nx >= m: continue
        if board[ny][nx] == '.' and bomb[y][x] < bomb[ny][nx]:
            bomb[ny][nx] = bomb[y][x]
            queue.appendleft((bomb[ny][nx], ny, nx))
 
    # d 워프 뛰며 탐색    
    for ddy,ddx in ((0,d), (0,-d), (-d,0), (d,0)):
        for i in range(-d+1, d):
            ny = y + ddy + (i if ddy == 0 else 0) 
            nx = x + ddx + (i if ddx == 0 else 0)
 
            # 범위 넘어간 경우 경계로 설정
            if ny < 0 or nx < 0 or ny >= n or nx >=m: 
                ny = max(0, ny)
                nx = max(0, nx)
                ny = min(ny, n - 1)
                nx = min(nx, m - 1)
 
            if bomb[y][x] + 1 < bomb[ny][nx]:
                bomb[ny][nx] = bomb[y][x] + 1
                queue.append((bomb[ny][nx], ny, nx))
 
print(bomb[n-1][m-1])
 
 

 

 

🍭 시행착오

 

 

 

0-1 bfs: 1436 ms

데이크스트라: 1768 ms

 

🔗 문제링크