백준: 16933 벽 부수고 이동하기 3

문제

16933번: 벽 부수고 이동하기 3

 

문제 풀이

 앞서 다룬 문제인 벽 부수고 이동하기 2 문제에서 낮에만 벽을 부술 수 있고, 밤에는 벽을 부술 수 없다는 조건이 추가된 문제이다. 문제를 풀기 위해서는 토마토 문제와 같이 하루에 발생할 수 있는 모든 경우의 수를 처리하여야 하므로, day 2 추가된 경우의 수가 3이라면 하루 동안 처리 되도록 하여야 한다. 이는 큐의 길이만큼 처리하는 방식을 사용하면 된다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, w):
    return 0 <= x < n and 0 <= y < m and not visited[x][y][w]


def bfs(start):
    q = deque([start])
    dirs = ((-1, 0), (0, 1), (1, 0), (0, -1))
    day = 1

    while q:
        night = False if day > 0 else True

        for _ in range(len(q)):
            cur_x, cur_y, wall = q.popleft()
            today = abs(day)

            if [cur_x, cur_y] == [n - 1, m - 1]:
                return today

            for x, y in dirs:
                next_x, next_y = cur_x + x, cur_y + y
                if visitable(next_x, next_y, wall):
                    if not graph[next_x][next_y]:
                        visited[next_x][next_y][wall] = today + 1
                        q.append((next_x, next_y, wall))
                    elif wall < k and not visited[next_x][next_y][wall + 1]:
                        if not night:
                            visited[next_x][next_y][wall + 1] = today + 1
                            q.append((next_x, next_y, wall + 1))
                        else:
                            q.append((cur_x, cur_y, wall))

        day = day + 1 if day > 0 else day - 1
        day *= -1

    return -1


if __name__ == '__main__':
    n, m, k = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().strip())) for _ in range(n)]
    visited = [[[0] * (k + 1) for _ in range(m)] for _ in range(n)]
    visited[0][0] = [1] * (k + 1)
    print(bfs((0, 0, 0)))

 낮과 밤은 현재 날짜가 양수이면 낮, 음수이면 밤으로 구분하도록 하였다. 이 문제 역시 파이썬으로는 통과하지 못하며 PyPy3로 제출하여야 한다. 17%에서 계속 시간초과가 나서 확인해 보니, 벽인 경우에 재방문 여부를 체크하지 않아 시간 초과가 발생하였다.

최초에 작성한 코드의 결과

 

위의 코드로 실행한 결과

 최대한 조건 판단을 줄이고, 이리저리 수정한 결과 초기에 작성하였을 때 보다, 시간과 메모리 사용량을 줄일 수 있었다.