파이썬 시간초과의 늪..(골드3)

14442번 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442

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

유사 문제가 존재하고, 풀어본 경험이 있어 금방 눈치챌 수 있었다.

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

2206번: 벽 부수고 이동하기

벽을 부술 때 마다 차원을 달리한다고 생각하면 된다. (멀티버스같은..?)

2206문제에서는 벽을 한번 부술 수 있어서 차원이 2개만 존재하면 충분했는데

이번 문제에서는 벽을 부술 수 있는 횟수가 변한다.

때문에 차원을 가변적으로 설정하면 된다.

import collections

def solve(x,y):
    que = collections.deque()
    que.append([x,y, 0, 1])
    visited[0][x][y] = 1
    while que:
        x, y, w, d = que.popleft()
        if x == N-1 and y == M-1:
            return d
        for dx, dy in move:
            nx, ny = x+dx, y+dy
            if 0 <= nx <= N-1 and 0 <= ny <= M-1:
                if maps[nx][ny] == 1 and w < K and not visited[w+1][nx][ny]:
                    que.append([nx, ny, w+1, d+1])
                    visited[w+1][nx][ny] = 1
                elif maps[nx][ny] == 0 and not visited[w][nx][ny]:
                    que.append([nx, ny, w, d+1])
                    visited[w][nx][ny] = 1

    return -1


N, M, K = map(int, input().split())
maps = [list(map(int, input().strip())) for _ in range(N)]
visited = [[[0]*M for _ in range(N)] for __ in range(K+1)]
move = [[1,0],[0,1],[-1,0],[0,-1]]
print(solve(0,0))

시간초과로 진짜 개고생했다

뭘 바꿔도 시간초과가 반복되 진짜 죽을지경이었다.

 

내가 찾은 문제는 두가지였다.

 

1. 방문노드를 기록할 때, True/False 보다는 1/0이 훨씬 빠르다.

2. 방문기록 리스트에 노드간 비용을 기록하고, 마지막에 값을 호출하는 경우가 있는데, 그냥 que에 저장할 때(bfs) 비용값도 같이 기록하는게 더 빠르다.

 

그냥.. 처음 내가 떠올린 감각을 따라가는게 가장 좋은 것 같다.

여기저기 알아보다가 이런저런 아이디어가 겹치면

코드는 복잡해진다.

 

슬프기도 했지만 홀가분한 문제였다.