[백준5014&파이썬] BFS은 1차원에서도 최단거리를 구할 수 있다.

# 문제

백준 5014 스타트링크 파이썬 풀이

5014번: 스타트링크

# 코드

import sys
from collections import deque

FAIL = "use the stairs"

F, S, G, U, D = map(int, sys.stdin.readline().split())
# 건물 높이 F
# 현재 위치 S
# 목표 지점 G
# 위로 U층 이동
# 아래로 D층 이동

dirs = [
  U, (-1*D)
]
# print(dirs)
visit = [False] * (F+1)
visit[0] = True # 0은 사용 안함

dq = deque()
dq.append((S,0)) # 현재 위치 삽입, 횟수
visit[S] = True

cnt = 0
while len(dq) != 0 :
  cur = dq.popleft()
  if cur[0] == G:
    print(cur[1])
    exit()
  # print(cur)

  for dir in dirs:
    next = (cur[0] + dir, cur[1] + 1 )
    if 1 <= next[0] <= F :
      if visit[next[0]] == False :
        # 다음으로 이동
        dq.append(next)
        visit[next[0]] = True

        # print("next : " , next)

        if next[0] == G :
          print(next[1])
          exit()

print(FAIL)

 

# 풀이

## 기억났던 문제

1697번: 숨바꼭질

• 옛날에 숨바꼭질 문제와 아주 유사했다. 이때는 DP를 공부했던 터라 이런거 보면 무조건 DP로 덤벼들었는데 그때는 DP로 풀다가 결국 못풀었던 기억이 있었다. 그리고 BFS로 풀어야 함을 알았고 BFS에서 이전 단계를 기억시키는 법을 통해 최단거리를 얻는 방법을 공부할 수 있었다. 

dq = deque()
dq.append((S,0)) # 현재 위치 삽입, 횟수

• 위 처럼, 튜플 형태로 만들고 두번째에는 횟수를 기억하게 하는 방법이다.
• 이번에는 문제를 풀면서 딱 해당 문제가 바로 스쳐지나갔었다.

 

## 1차원에서 이동과 최단거리를 구할 수 있다.

• 엘리베이터는 U층과 D층으로 위로 또는 아래로 이동한다. 2차원에서 이동을 ( x, y ) 와 같은 형식으로 표현해 dirs를 만들어 사용했었다.
• 이번 문제는 튜플이 아니라 그냥 U , -1 * D 로 dirs를 만들었다.

dirs = [
  U, (-1*D)
]

• 1차원에서의 최단거리를 구할 수 있다는 생각만 할 수 있다면 그렇게 특별할 것 없는 문제 같다.