[Python] 백준 5014 스타트링크

 

문제 분석

• 총 F층,
• 가려는 건물은 G층,
• 현재 S층
  
  
• 버튼은 U : 위로, D : 아래로 (이동할 수 없으면 움직이지 않는다.)
• G층에 도착하려면 버튼을 적어도 몇 번 눌러야 하는가
• 갈 수 없으면 "use the stairs" 출력
• S -> G로 가기 위해 눌러야 하는 버튼의 수의 최솟값 출력

 

풀이

• s + u * i - d * j = g 를 만들 수 있는 ( i + j )의 최솟값을 찾아라
• 단, 모든 과정에서 값은 1 이상 f 이하를 벗어날 수 없다.
• 백트래킹
• 이동 횟수 : 이전 층 + 1
• 시작 층을 큐에 넣고
• 만약 큐가 비었는데도 끝나지 않았다면, 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

highest, now, end, up, down = map(int, input().split())
check = [0 for _ in range(highest+1)] # 층은 아직 방문하지 않았으므로 0, 층은 1층부터

def bfs() :
    q = deque()
    q.append(now)
    check[now] = 1 # 시작 1

    while q :
        current = q.popleft()

        if current == end :
            return check[current]-1
        else :
            for next in (current + up, current-down) :
                if (0 < next <= highest) and check[next] == 0:
                    check[next] = check[current] + 1
                    q.append(next)
    # 큐를 다 돌았는데도 도달하지 못하면
    return "use the stairs"

print(bfs())

 

 

2회차 - 25.03.21

import sys
input = sys.stdin.readline
from collections import deque

height, now, arrival, up, down = map(int, input().split())
building = [i for i in range(height+1)]
v = [False for _ in range(height+1)] # 1 ~ height 층

def dfs() :
    d = deque()
    d.append((now, 0))
    v[now] = True

    while d :
        current, cnt = d.popleft()

        if current == arrival :
            print(cnt)
            return

        for move in (current+up, current-down) :
            # 범위 먼저 확인..
            if 1 <= move <= height and not v[move] : # 아직 방문 x, 갈 수 있는 층이면
                d.append((move, cnt+1))
                v[move] = True

    print('use the stairs')
    return

dfs()