[BOJ 5014] 스타트링크 (Python3)

www.acmicpc.net/problem/5014

5014번: 스타트링크

 

from collections import deque
 
F, S, G, U, D=map(int, input().split())
dist=[0]*(F+1)
 
def bfs():
    if S==G:
        return 0
    else:
        queue=deque([S])
        dist[S]=1
        while queue:
            x=queue.popleft()
            if x+U==G or x-D==G:
                return dist[x] 
            for i in (x+U, x-D):
                if i<=0 or i>F or dist[i]!=0:
                    continue
                dist[i]=dist[x]+1
                queue.append(i)
    return "use the stairs"
 
print(bfs())
 

 

BOJ 1697번(숨바꼭질) 과 상당히 유사한 문제.

이 문제 역시 BFS 이다.

처음엔 첫 시작점 방문처리를 안해줘서 AC를 못받았다.

 

dist배열의 초기값을 -1로 설정해두면 헷갈리지 않고 좋을 듯.

그러면 첫 시작점 거리를 0으로 설정할 수 있어 좋다.

 

시작점을 방문처리 하고->시작점에 인접한 U, D가 조건에 맞으면(한번도 방문을 안하고, 범위를 넘지 않을 경우) dist 배열의 x 인덱스의 값에 +1을 해줘서 한 번 이동했다는 걸 표시한다. 인접 노드도 큐에 넣어 그 다음 인접 노드, 그 다음 인접 노드.. 체크하여 각 거리값(dist배열)을 업데이트한다.

목적지 노드가 나올 경우 dist 배열 값을 바로 리턴한다. 이때 +1 안하고 바로 리턴한 이유는 시작점 dist를 1로 시작했기 때문에.. 다음엔 -1로 하자. 그래야 안헷갈린다.