[파이썬] 백준 5014 : 스타트링크 (실버1)

[파이썬] 백준 5014 : 스타트링크 (실버1)

 

5014번: 스타트링크

---

문제

테스트 케이스

# 10 1 10 2 1 -> 6
# 100 2 1 1 0 -> x
# 50000 25000 25001 25001 25001 -> x
# 999990 999990 999890 10 110 -> 2
# 1000000 1000000 1 0 1 -> 999999
# 100 1 1 13 7 -> 0
# 2 2 1 0 1 -> 1
# 5 1 1 2 2 -> 0
# 1 1 1 1 1 -> 0

---

풀이

0. 방향성 생각

전형적인 BFS 문제. 최단거리 문제

큐에 넣고 범위 내에 들어왔을 때 탐색을 진행해주면 된다.

같은 층에 있을 때 0으로 출력하는 엣지 케이스가 존재한다

 

1. BFS 함수정의

from collections import deque
h,s,e,u,d = map(int,input().split())

arr = [-1]*(h+1)

def bfs(start) :
    q = deque()
    q.append(start)
    arr[start] = 0
    while q: 
        x = q.popleft()
        
        for nx in (x+u,x-d):
            if 1<=nx<=h :
                if arr[nx] == -1 :
                    arr[nx] = arr[x]+1
                    q.append(nx)
                if nx == e :
                    return arr[nx]

높이가 h이므로 0층부터 1층까지 만들어준다. 0층은 필요없는 더미 인덱스

큐에 넣고 돌릴 때 시작지점 0으로 초기화 시켜주고 시작

범위 내에 들어오고 탐색 안했을 때 걸린 시간 업데이트 해주기.

탐색 후 도착했으면 리턴해준다.

2. 출력

answer = bfs(s)
if s==e :
    print(0)
else :
    if answer == None :
        print('use the stairs')
    else :
        print(answer)

사실 여기서 s==e 조건을 안걸어서 33%쯤에서 한 번 틀렸다.

33%에서 # 1 1 1 1 1 -> 0 엣지케이스가 이렇게 들어가 있는 듯 하다. 조건을 안걸어주면 use the stairs로 나온다.

 

# 5 1 1 2 2 -> 0 같이 다른 층을 탐색할 수 있는 경우에는 올바르게 답이 나온다.

 

---

전체코드

from collections import deque
h,s,e,u,d = map(int,input().split())

arr = [-1]*(h+1)

def bfs(start) :
    q = deque()
    q.append(start)
    arr[start] = 0
    while q: 
        x = q.popleft()
        
        for nx in (x+u,x-d):
            if 1<=nx<=h :
                if arr[nx] == -1 :
                    arr[nx] = arr[x]+1
                    q.append(nx)
                if nx == e :
                    return arr[nx]
answer = bfs(s)
if s==e :
    print(0)
else :
    if answer == None :
        print('use the stairs')
    else :
        print(answer)

자꾸 코드길이 신경쓰여서 일반적인 코드로 깔끔하게 짜려고 하다가 틀리는데

그냥 눈에 보이는 엣지케이스 같은 경우에는 바로 짤라내고 시작하는게 나은듯