[백준] 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

시간초과로 고생을 꽤나 한 문제입니다. 처음에 접근은 BFS + 우선순위 큐를 사용하여 현재 위치에 도달할 수 있는 최소값만을 선택해서 dist 2차원 배열에 저장하는 방식으로 풀이했습니다. 하지만 이런 방식을 사용하면 우선순위 큐에 push하는데 O(log n)만큼의 시간이 소요되기 때문에 시간초과가 발생했습니다. 

 

1. 제가 지나쳤던 부분은 BFS를 통해 탐색했을 때 큐에서 목표지점에 도달하는 순간이 가장 짧은 거리를 보장한다는 것이었습니다. 몇번을 부쉈든간에 목표지점이 큐에서 나오는 순간 해당 거리가 짧은 거리가 된다는 것입니다. 

 

2. 3차원 visited가 필요한 이유는 무엇인가입니다. 다음과 같은 예가 있다고 생각해봅시다.

0 1 1

1 0 1
1 1 1

1 1 0

 

만약, 3개의 벽을 깰 수 있고 (1, 2) 위치에 (0, 0) -> (0, 1) -> (0, 2) -> (1, 2)를 통해 먼저 도달했다고 가정했을 때 2차원 visited[1][2]에는 true로 변경되었으나 벽을 3개 모두 깼기 때문에 더이상 탐색을 진행할 수 없습니다. 뒤늦게 큐에서 나온 (0, 0) -> (1, 0) -> (1, 1) -> (1, 2)는 아직 벽을 더 깰 수 있음에도 visited[1][2]가 true이기 때문에 방문하지 않습니다. 이런 경우를 방지하기 위해 3차원 배열을 통하여 몇 개의 벽을 깨고 현재 위치에 도달했는지를 체크해야합니다. (0, 0) -> (0, 1) -> (0, 2) -> (1, 2)는 visited[3][1][2]가 true로 만드므로 (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) visited[2][1][2]는 false 이므로 더 탐색이 가능합니다. 이 때문에 3차원 visited 배열이 필요로 하게 됩니다.

 

import sys
from collections import deque

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

INT_MAX = sys.maxsize

# n: 행의 수, m: 열의 수, k: 부술 수 있는 벽의 수
n, m, K = tuple(map(int, input().split()))

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

board = [
    list(map(int, input().rstrip()))
    for _ in range(n)
]

# visited[k][i][j] : k번 벽을 깼을 때 도달했는지 여부
visited = [
    [[False] * m
    for _ in range(n)]
    for __ in range(K + 1)
]

# 벽을 몇개를 깨든 원점에 도달할 수 있는 최소 거리는 1
visited[0][0][0] = True
q = deque([(1, 0, 0, 0)])

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

ans = INT_MAX

while q:
    d, k, y, x = q.popleft()
    if y == n - 1 and x == m - 1:
        ans = d
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if inRange(ny, nx):
            # 다음 위치가 벽인 경우
            if board[ny][nx] == 1:
                if k < K and not visited[k + 1][ny][nx]:
                    visited[k + 1][ny][nx] = True
                    q.append((d + 1, k + 1, ny, nx))

            # 다음 위치가 벽이 아닌 경우
            else:
                if not visited[k][ny][nx]:
                    visited[k][ny][nx] = True
                    q.append((d + 1, k, ny, nx))

if ans == INT_MAX:
    print(-1)
else:
    print(ans)

 

조금 더 개선된 풀이입니다. 3차원 visited 대신 2차원 wall 배열로 수정하였습니다. 현재 위치에 더 적은 벽을 깨고 도착했다는 것은 더 나은 상황에서 탐색이 가능하다는 말과 같습니다. 위의 케이스에서 wall[1][2] = 3이지만 뒤에 도착한 거리가 2이므로 wall[1][2] = 2로 갱신하고 탐색을 하게 되기 때문에 최단 거리를 얻을 수 있습니다.

 

import sys
from collections import deque

# sys.stdin = open("input1.txt", "r")

input = sys.stdin.readline

INT_MAX = sys.maxsize

# n: 행의 수, m: 열의 수, k: 부술 수 있는 벽의 수
n, m, K = tuple(map(int, input().split()))

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

board = [
    list(map(int, input().rstrip()))
    for _ in range(n)
]

# wall[i][j] : (i, j)에 도달했을 때 깨야하는 최소 벽의 개수
wall = [
    [INT_MAX] * m
    for _ in range(n)
]

# 원점에 도달하기 위해 깨야하는 벽의 개수는 0개
wall[0][0] = 0
q = deque([(1, 0, 0, 0)])

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

ans = INT_MAX

while q:
    d, k, y, x = q.popleft()

    # 현재 (y, x)에 도달하기 위한 최소 벽의 개수가 갱신된 경우에는 지나친다.
    if k > wall[y][x]:
        continue

    if y == n - 1 and x == m - 1:
        ans = d
        break

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if inRange(ny, nx):
            # 다음 위치가 벽인 경우
            if board[ny][nx] == 1:
                if k < K and wall[ny][nx] > k + 1:
                    wall[ny][nx] = k + 1
                    q.append((d + 1, k + 1, ny, nx))

            # 다음 위치가 벽이 아닌 경우
            else:
                if wall[ny][nx] > k:
                    wall[ny][nx] = k
                    q.append((d + 1, k, ny, nx))

if ans == INT_MAX:
    print(-1)
else:
    print(ans)

 

이전 풀이

개선된 풀이

python3로 제출하면 어떤 풀이던 시간초과가 나긴 합니다..