9376번 - 탈옥
모든 반례 다 통과해도 10%에서 틀리는 경우
벽을 만나느 경우('#') 와 문이 없는 경우 ('.') 중 후자를 우선탐색 해야합니다.
저는 파이썬 deque를 사용해서 구현했는데, 이 때 bfs 함수에서 '#'일 때에는 `append`를, '.'인 경우에는 `appendleft`를 사용했습니다.
if arr[ny][nx] == '#': cnt[ny][nx] = cnt[y][x] + 1 q.append([ny, nx]) if arr[ny][nx] == '.' or arr[ny][nx] == '$': cnt[ny][nx] = cnt[y][x] q.appendleft([ny, nx]) # 문이 없는 경로는 우선적으로 처리하도록 deque의 왼쪽에 추가
이렇게 하니까 시간 초과가 해결되었습니다 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
leedrkr323 2년 전 1
모든 반례 다 통과해도 10%에서 틀리는 경우
벽을 만나느 경우('#') 와 문이 없는 경우 ('.') 중 후자를 우선탐색 해야합니다.
저는 파이썬 deque를 사용해서 구현했는데, 이 때 bfs 함수에서 '#'일 때에는 `append`를, '.'인 경우에는 `appendleft`를 사용했습니다.
if arr[ny][nx] == '#': cnt[ny][nx] = cnt[y][x] + 1 q.append([ny, nx]) if arr[ny][nx] == '.' or arr[ny][nx] == '$': cnt[ny][nx] = cnt[y][x] q.appendleft([ny, nx]) # 문이 없는 경로는 우선적으로 처리하도록 deque의 왼쪽에 추가