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

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

5014번: 스타트링크

이 문제는 길찾기 문제인데

엘리베이터로 되어있는 독특한 문제.

현재 시작점이 S이고

U는 위로 가는 거

D는 아래로 가는 거

이렇게 각각 구현해주고

BFS를 구현해주면 됩니다.

 

#백준 5014번 스타트 링크
from collections import deque

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


visited=[False]*(F+1)

q=deque()
q.append([S,0])
visited[S]=True
direct=[U,D]#for문으로 돌리기 위해 direct라는 리스트로 받아줌
answer=-1

while q:
    now,n_cnt=q.popleft()
    if now==G:
        answer=n_cnt
        break
    for d in range(2):
        if direct[d]==0:
            continue
        go=now+direct[d]*(-1)**(d) #위,아래 가는 걸 구현하기 위해, d=0일때는 U이므로 0제곱, d=1일때는 D이므로 1제곱해줘서 위 아래 이동 구현

        if 0<go<=F and visited[go]==False:
            visited[go]=True
            q.append([go,n_cnt+1])


if answer==-1:
    print("use the stairs")
else:
    print(answer)

 

저는 처음에 이 코드에서

answer=0으로 초기화 시킨 다음

answer=0일 때

계단을 이용해라를 출력했습니다.

그랬더니 해당 코드가 오답으로 나왔습니다.

반례를 고민하다가 처음 주어질 때

S=G인 경우를 생각했습니다.

예를들면

10 1 1 2 2 

이렇게 주어질 때죠.

이때는 answer=0이 나오는 게 당연합니다.

왜냐하면 이미 G가 있는 층에 왔는데

버튼을 0번 누르면 되기 때문이죠.

하지만 저는 처음에

answer=0일 때 계단을 이용하라고 출력했으므로

오답이 발생했습니다.

그래서 이후에 answer=-1로 초기화하여 제출하니

정답으로 인식해서 통과했습니다.

반례를 찾을 때 어떤 케이스를 생각하면 좋을지

고민하게 만들어준 문제입니다.