[백준/Python] DFS/BFS-5014번. 스타트링크

📌 문제 링크:

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

✅ 문제 유형: BFS/DFS

✅ 풀이 방법

• 버튼을 누르는 최소 횟수를 구하는 것이므로 BFS를 사용한다. 
• 📢 visited를 선언해, 여기에 버튼을 누른 횟수를 저장해 나가면 된다. 
• 틀렸던 이유
  • U 또는 D가 0이라서 그 다음 위치가 S층과 똑같은 경우는 고려할 필요가 없다. 
  • 📢 (반례) 예를 들어, F = 2, S =  2, G = 1, U = 0, D = 1일 때
    • 최대 2층인 건물에서, 현재 위치 2층이고 목적지는 1층이다.
    • 이때 U가 0이므로 위로 올라갈 방법은 없고, 아래로 1층 내려가는 것 뿐이다. 
    • 그 다음 위치 후보지는 [s+u, s-d] = [2, 1] 일 때 큐에는 2와 1이 저장된다.
    • 📢 단, 현재 위치가 2층인데 또 2층을 방문해 버튼을 눌렀다는 횟수를 세는 것은 말이 안된다.
    • 이러한 반례를 생각해낼 수 있어야 한다. 

 

📌 풀이 코드 

# 최소 몇 번을 눌러야 하는지이다. BFS 해당 
F, S, G, U, D = map(int, input().split())
# G층에 가야하고, S층에 현재 있음
# 위로 U, 아래로 D 최대 F층까지 있음

q = [] 
visited = [0 for _ in range(F+1)]
answer = 0
def bfs(s):
    global answer
    q.append(s)
    while q:
        v = q.pop(0)
        if v == G: 
            return visited[v]
        for nv in [v+U, v-D]:
            if 1<=nv<=F and not visited[nv] and nv != s: # 포인트: 만약, u,d가 0이라서 nv가 원래 위치일때는 고려할 이유가 X
                q.append(nv)
                visited[nv] = visited[v] + 1
                #print(f"\tAPPEND {nv} button={visited[nv]}")
    return "use the stairs"
print(bfs(S))