문제 5014 스타링크

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

My Code

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

F, S, G, U, D = map(int, input().split())

count = [0] * (F+1)

def bfs(v):
    queue = deque()
    queue.append(v)
    
    while queue:
        x = queue.popleft()
        if x == G:
            return count[G]
        for i in (x+U, x-D):
            if 0 < i <= F and count[i] == 0:
                count[i] = count[x]+1
                queue.append(i)
    if count[G] == 0:
        return "use the stairs"

print(bfs(S))

Solution

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

F, S, G, U, D = map(int, input().split())

visited = [0] * (F+1)
count = [0] * (F+1)

def bfs(v):
    visited[v] = 1
    queue = deque()
    queue.append(v)
    
    while queue:
        x = queue.popleft()
        if x == G:
            return count[G]
        for i in (x+U, x-D):
            if 0 < i <= F and visited[i] == 0:
                visited[i] = 1
                count[i] = count[x]+1
                queue.append(i)
    if count[G] == 0:
        return "use the stairs"

print(bfs(S))

배운점

일단 풀이는 방문을 체크할 visited와 눌러야할 버튼수를 계산할 count를 만들어주고
bfs알고리즘을 통해 풀이하였다.
헷갈렸던 점은 for i in (x+U, x-D) 이 부분인데 예를들어 (3, 0)이면 i는 3, 0이 순서대로 들어가는 것을 몰랐다.
그저 range나 만들어진 리스트를 순서대로 반복하는 것만 해봤지 두 개의 수를 각각 반복하는건 처음 보는 방식이라 풀이를 보고 직접 예시를 넣어본 뒤 알게되었다.
나머지는 기존에 풀던 bfs문제들과 크게 다른점이 없어서 쉽게 이해되었다.

내 코드에선 3 3 1 0 1이 반례로 작용된다.
3층에서 1층까지 다운 두 번이면 스타링크에 도달 할 수 있는데 출력은 3이 나온다.
그 이유는 up이 0일 경우에 count[3] = 1이 되고 down하면 이미 count[2] = count[3]+1이 되므로 2가 들어간다. 한 칸 이동 했는데 2번 이동이 된 셈이다(즉 up이 제자리 이동으로 기록된것.)
하지만 Solution에서 visited[3]에 1을 넣고 시작하면 up한 뒤 visited[3] == 0이 아니기 때문에 건너 뛰게 된다.
제자리 이동이 가능한 반례가 존재해서 틀렸다.
방문처리를 따로 하고싶으면 visited = [0] * (F+1)리스트를 하나 더 만들어주면 된다.
이 점 주의해야 겠다.!!