작성
·
311
0
고민해보았지만, 제 코드가 왜 시간초과 나는지 이유를 알 수 없어서, 답답한 마음에 질문드립니다.
[시간 복잡도]
- 각 좌표 정보 얻기 위한 이중포문 10^6
- visit 이차원 배열 2개 생성 2*10^3
- bfs1 10^6(최대)
- bfs2 10^6(최대)
- 총 3*10^6 + 2*10^3
- 위처럼 계산하면 시간 초과가 발생하지 않아야 하나, 발생하며
- 위에 적은 것에서 bfs2는 우선순위큐를 사용하기에 더더욱 연산횟수가 줄어들것이라 생각하였습니다.
왜 시간 초과가 발생한 걸까요ㅠ
import sys
input = sys.stdin.readline
from collections import deque
import heapq
d = [(0,1),(0,-1),(1,0),(-1,0)]
# 영희 시작점 -> 산딸기 전체 탐색
def bfs1():
q = deque([(sx,sy)])
visit1[sx][sy]=1
while q:
x,y = q.popleft()
for dx,dy in d:
nx = x + dx
ny = y + dy
if 0<=nx<N and 0<=ny<M and visit1[nx][ny]>visit1[x][y]+1 and arr[nx][ny]!=1:
visit1[nx][ny]=visit1[x][y]+1
q.append((nx,ny))
# 각 산딸기 -> 기사
# 우선순위큐를 활용, 어느 산딸기 위치에서 시작하든 최단 거리로 도달할 수 있도록
def bfs2():
h = []
for x,y in raspberry:
heapq.heappush(h,(visit1[x][y]-1, x,y))
visit2[x][y]=visit1[x][y]-1
while h:
dist, x, y = heapq.heappop(h)
if visit2[x][y]<dist:
continue
if (x,y)==(ex,ey):
return dist
for dx,dy in d:
nx,ny = x + dx,y+dy
if 0<=nx<N and 0<=ny<M and arr[nx][ny]!=1 and visit2[nx][ny]>dist+1:
visit2[nx][ny] = dist+1
heapq.heappush(h,(dist+1,nx,ny))
# 입력
M,N = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
sx,sy,ex,ey=0,0,0,0
raspberry = []
for i in range(N):
for j in range(M):
if arr[i][j]==2:
sx,sy = i,j
elif arr[i][j]==3:
ex,ey = i,j
elif arr[i][j]==4:
raspberry.append((i,j))
visit1 = [[float('inf')]*M for _ in range(N)]
visit2 = [[float('inf')] * M for _ in range(N)]
bfs1()
print(bfs2())
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
야옹님이 고민하신 시간 복잡도 계산에도 불구하고 코드가 시간초과가 나는 문제를 해결하기 위해서는 몇 가지 추가적으로 고려해볼 점이 있습니다.
첫째, Python에서는 BFS를 구현할 때 deque를 사용하는 것이 좋지만, 복잡한 자료구조인 heapq의 사용이 오히려 오버헤드를 발생시킬 수 있습니다. heapq를 사용할 경우 힙의 속성을 유지하기 위한 추가 연산이 필요하기 때문에, 실제 연산 시간이 빅오 표현상의 시간 복잡도보다 길어질 수 있습니다.
둘째, Python의 기본 인터프리터인 CPython의 경우 실행 속도가 상대적으로 느릴 수 있습니다. PyPy 같은 Just-In-Time 컴파일 기반의 인터프리터를 사용하는 것도 좋은 방법일 수 있습니다.
셋째, 시간 초과 문제를 해결하기 위해서는 알고리즘 자체를 최적화해야 할 수도 있습니다. 예를 들어, 공간 복잡도를 줄이기 위해 필요 없는 정보는 저장하지 않거나, 코드 내의 다른 부분에서 불필요하게 반복되는 연산을 줄일 수 있는지 검토해보시는 것이 좋습니다.
시간초과 문제는 알고리즘의 효율성을 높이거나, 보다 빠른 자료구조를 사용하는 것으로 접근할 수 있습니다. 이미지나 추가적인 정보가 필요하시면 아래 링크를 참고하시기 바랍니다.
원하는 답변을 찾지 못하셨다면, 인프런의 ‘문의하기’ 기능을 통해 더 상세한 도움을 받아보시는 방법도 있습니다. 최대한 빠르게 답변드리도록 하겠습니다!
인프런 FAQ 문의하기 링크:
인프런 문의하기