인프런 커뮤니티 질문&답변

야옹님의 프로필 이미지
야옹

작성한 질문수

코딩테스트 실전 모의고사(with C++) : 대기업 대비

4. 숲속의 기사 문제해설(BFS)

[2-4 숲속의기사]

작성

·

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 문의하기 링크:
인프런 문의하기

야옹님의 프로필 이미지
야옹

작성한 질문수

질문하기