[bfs/백준] 5014번 : 스타트링크

- 문제 : https://www.acmicpc.net/problem/5014

 

문제 이해 

- 1 부터 building 까지의 범위 안에서 current에서 company로 이동하는 최소 칸 수를 출력하는 문제다. 

- 이동은 한 번에 +u 또는 -d로 진행된다. 

 

풀이 로직 

- 입력값들을 받은 다음 arr를 설정해준다. 

- queue를 가지고 bfs를 진행하는데 현재 있는 노드가 company라면 while문을 종료한다. 

- 현재 있는 노드가 company가 아니라면 u와 d로 이동하면서 범위 내의 방문하지 않은 노드들 위주로 탐색한다.

- 이동하면서 이전에 방문하지 않은 노드들을 탐색하면서 이전 노드의 값 + 1(arr[x] + 1)로 업데이트 해준다. 

- 반복문이 종료된 뒤 arr[company] 값에 따라 출력을 다르게 해주면 된다.

 

정답 풀이 

고려하지 않아도 될 상황을 고려해서 시간초과가 많이 발생했는데, 이 문제는 단순 bfs로 풀면 되기 때문에 방문하지 않은 노드들에 대해서만 진행하면 된다.

building, current, company, u, d = map(int, input().split())

arr = [0] * (building + 1)
arr[current] = 1
queue = [current]
while queue:
    x = queue.pop(0)
    
    if x == company:
        break
        
    for nx in [x + u, x - d]:
        if 1 <= nx <= building :
            if not arr[nx]:
                arr[nx] = arr[x] + 1
                queue.append(nx)
            
if arr[company] == 0:
    print("use the stairs")
else:
    print(arr[company] - 1)