BFS - 스타트링크 [5014번]

어제도 BFS 문제를 풀면서 아래 첫번째 코드 처럼 q에 [현재 층수, 움직인 횟수] 형태로 append하였더니 시간초과가 나왔다.

deque로 BFS 문제를 풀때는 방문 여부를 처리하는 부분이 별개로 필요하다는 것을 다시 한번 깨닫게 하였다.

F, S, G, U, D = map(int, input().split())

from collections import deque
q = deque([(S, 0)])

tmp = []
if U > 0:
    tmp.append(U)
if D > 0:
    tmp.append(-1 * D)

chk = False
while q:
    floor, cnt = q.popleft()
    if floor == G:
        chk = True
        break
    
    for a in tmp:
        f = floor + a
        if 1 <= f <= F:
            q.append((f, cnt+1))
            
if chk == False:
    print("use the stairs")

 

아래 코드가  테스트를 통과한 코드이다.

F, S, G, U, D = map(int, input().split())

from collections import deque
q = deque([S])
visited = [0 for _ in range(F+1)]

tmp = []
if U > 0:
    tmp.append(U)
if D > 0:
    tmp.append(-1 * D)

chk = False
while q:
    floor = q.popleft()
    if floor == G:
        print(visited[floor])
        chk = True
        break
        
    for a in tmp:
        f = floor + a
        if 1 <= f <= F and not visited[f]:
            q.append(f)
            visited[f] = visited[floor]+1
            
if chk == False:
    print("use the stairs")