문제 분석

벽 부수고 이동하기 시리즈의 이전 문제와 마찬가지로 주어진 미로 안에서 최대 k번 벽을 부수고 이동할 수 있는데 낮/밤이 추가되어 낮에만 벽을 부술 수 있고, 제자리에서 기다리는 선택지가 추가되었다.

지금까지와 같은 맥락으로 배열을 1차원 늘려서 board[벽을 부순 횟수][x][y][낮/밤]을 만들어놓고 테이블을 채워나갔는데 시간초과와 메모리 초과가 발생했다. x, y, k가 각각 1000, 1000, 10까지 가능해서 board에 총 22,000,000개의 int값이 들어가는데, 파이썬에서는 int가 24바이트이기 때문에 입력만 받아도 제한 메모리인 512MB를 넘어가버린다.

그래서 다른 방법으로 문제를 접근하려 했지만 실패하고 풀이를 찾아 보았다

Key idea

문제 해결의 중심이 되는 아이디어는 미로의 크기와 같은 visited에 해당 위치에 도착할 때 까지 벽을 부순 횟수를 저장하는 것이다. 만약 같은 위치에 도달하는 방법이 여러개라면 그 중 벽을 가장 적게 부순 경로를 선택한다.

또한 낮/밤 모두 인접한 길이 있으면 진행하지만, 벽을 만나면 낮에는 무조건 벽을 부수고 밤에는 무조건 대기하는 방법으로 진행하면 최단경로로 목적지에 도착할 수 있다.

Solution

지금까지는 동시에 여러 위치에서 탐색을 돌리는 방법을 몰라서 이동 시간을 기록하기 위해 board에 직접 이동시간을 업데이트 했는데, 아래와 같이 while문 안에 큐의 길이만큼 for문을 추가하면 한 번에 여러개의 원소를 pop하는 것과 같은 효과를 내는 것을 알았다. 이 형식은 유용하게 쓰일 것 같다.

while q:
	for _ in range(len(q)):
    	...
    res += 1

위의 아이디어를 구현한 코드는 아래와 같다.

def bfs():
    if n == m == 1:
        return 1

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    q = deque()
    q.append((0, 0, 0))
    res = 1

    night = False
    while q:
        for _ in range(len(q)):
            x, y, hop = q.popleft()

            if x == n-1 and y == m-1:
                return res

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

                if not (0 <= nx < n and 0 <= ny < m):
                    continue

                if visited[nx][ny] <= hop:
                    continue

                if not night:
                    if board[nx][ny] == 0:
                        visited[nx][ny] = hop
                        q.append((nx, ny, hop))
                    else:
                        if hop >= k:
                            continue
                        visited[nx][ny] = hop
                        q.append((nx, ny, hop + 1))
                else:
                    if board[nx][ny] == 0:
                        visited[nx][ny] = hop
                        q.append((nx, ny, hop))
                    else:
                        q.append((x, y, hop))
        night = not night
        res += 1

    return -1

n, m, k = map(int, sys.stdin.readline().strip().split(" "))
board = []
for _ in range(n):
    line = sys.stdin.readline().strip()
    tmp = []
    for c in line:
        tmp.append(int(c))
    board.append(tmp)

visited = [[k+1 for _ in range(m)] for _ in range(n)]
visited[0][0] = 0

print(bfs())

• BOJ 16933 벽 부수고 이동하기 3