[백준]5014(파이썬) - 스타트링크

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

• 이 문제는 보자마자 BFS로 풀어야겠다는 생각이 들었습니다. 또 생각이 들었던 점은 뱀과 주사위 게임과 거의 유사한 유형이라는 점입니다.
• 이 문제의 핵심은 BFS 떠올렸어? 그리고 UP, DOWN을 어떻게 표현할래?라고 생각합니다. 이 부분만 인지를 했으면 문제 푸는 데는 어렵지 않았습니다.
• 한 가지, result를 -1로 초기화하지 않고 0으로 초기화한 뒤, result [s-1] = 0을 제외시키면 31 퍼센트에서 틀렸습니다 가 나오는데 왜인지 이유를 생각을 해보고 있습니다. 이유를 알게 되면 게시물에 추가해놓을 예정입니다.
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

 

import sys
input = sys.stdin.readline
from collections import deque
f,s,g,u,d = map(int,input().split())

# 층 방문을 체크하기 위한 리스트
visited =  [0 for _ in range(f)]
# 각 층에 올 수 있는 방법들 중 최솟값을 기록하는 리스트
result = [-1 for _ in range(f)]
# 현재 위치를 0으로 시작
result[s-1] = 0
# 움직일 수 있는 방향, 위로 가는 u 과 아래로 가는 -d 로 생성.
dfloor = [u,-d]

# 나머지는 일반적인 최소거리를 구하는 bfs 구현
def bfs():
    q= deque()
    visited[s-1] = 1
    q.append(s-1)
    while q:
        floor = q.popleft()
        # u과 d 으로 갈 수 있는 층을 고려하는 구현
        for i in range(2):
            next_floor = floor + dfloor[i]
            if 0<=next_floor<f and visited[next_floor]==0:
                result[next_floor] = result[floor]+1
                q.append(next_floor)
                visited[next_floor] =1
bfs()
print(result[g-1] if result[g-1] != -1 else "use the stairs")

 

아래는 result를 0으로 초기화했을 때

 

import sys
input = sys.stdin.readline
from collections import deque
f,s,g,u,d = map(int,input().split())

visited =  [0 for _ in range(f)]
result = [0 for _ in range(f)]
# result[s-1] = 0
dfloor = [u,-d]

def bfs():
    q= deque()
    visited[s-1] = 1
    q.append(s-1)
    while q:
        floor = q.popleft()
        for i in range(2):
            next_floor = floor + dfloor[i]
            if 0<=next_floor<f and visited[next_floor]==0:
                result[next_floor] = result[floor]+1
                q.append(next_floor)
                visited[next_floor] =1
bfs()
print(result[g-1] if result[g-1] != 0 else "use the stairs")