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

스타트 링크

풀이

[[1697_숨바꼭질]] 문제와 유사하게 풀 수 있습니다.

• 방문한 층 수를 기억하기 위한 check 배열을 생성합니다.
• 시작점인 s를 queue에 넣어주고 이를 pop 하면서 queue에 대한 bfs 탐색을 시작합니다.
• queue에는 현재의 층 수가 저장되어 있기 때문에 이 층 수가 g가 될 때의 값을 찾으면 되고, queue가 모두 종료될 때 까지 답을 찾지 못한 경우 문제에서 요구한 use the stairs를 출력해주면 됩니다.
• 여기서 주의해야할 점은 처음에 시작한 지점을 먼저 시작했다고 1로 체크를 해주고, 마지막에 출력 시 출력 값에서 -1로 빼주어야 한다는 점입니다.
  • 예를 들어 입력이 10 10 1 0 1로 들어온 경우, 시작지점을 먼저 체크를 하지 않으면 10번 이동한 것으로 출력되지만 실제로는 9번만 이동합니다. 이 경우를 조심해야합니다. 저도 이 부분을 찾느라고 조금 시간이 걸렸습니다.

from collections import deque  
import sys  

"""  
f: 건물의 총 층 수  
s: 강호가 현재 있는 층 수  
g: 스타트링크의 층 수(타겟 층수)  
u: 위로 u층 만큼  
d: 아래로 d층 만큼  
"""  
sys.stdin = open("5014_스타트링크_input.txt", "r")  
f, s, g, u, d = map(int, sys.stdin.readline().split())  
check = [0 for _ in range(f + 1)]  


def bfs():  
    queue = deque()  
    queue.append(s)  

    check[s] = 1  

    while queue:  
        y = queue.popleft()  

        if y == g:  
            return check[y] - 1  
        else:  
            for x in (y + u, y - d):  
                if (0 < x <= f) and check[x] == 0:  
                    check[x] = check[y] + 1  
                    queue.append(x)  

    return "use the stairs"  


print(bfs())

• 문제를 풀 때, for loop의 범위를 어떻게 지정할까에 대한 고민을 하는데, 이 문제처럼 문제를 풀기 위해서 어떤 연산이 필요하다면 (단순 범위를 반복하는게 아니라면) 반복문의 범위에 해당 수식을 사용하는 것을 적극적으로 고려해봐야 할 것 같습니다.