[백준] 5014 : 스타트링크 python

 

[f+1][2] 크기의 visited라는 list를 생성하고

0번 열에 방문체크를, 1번 열에 버튼을 누른 횟수를 저장해서 풀었다.

 

from collections import deque

f,s,g,u,d = map(int,input().split())
visited=[[0 for j in range(2)]for i in range(f+1)]

def bfs(s,g):
    queue = deque()
    queue.append(s)
    visited[s][0]=1
    while queue:
        a = queue.popleft()
        # 목표 지점에 도달했으면 횟수를 출력하고 리턴
        if a==g:
            print(visited[a][1])
            return
        # 위에 아직 방문하지 않은 층이 있다면 이동
        if a+u<=f and visited[a+u][0]==0:
            queue.append(a+u)
            visited[a+u][0] = 1
            visited[a+u][1] = visited[a][1]+1
            
        # 아래에 아직 방문하지 않은 층이 있다면 이동
        if a-d>0 and visited[a-d][0]==0:
            queue.append(a-d)
            visited[a-d][0] = 1
            visited[a-d][1] = visited[a][1]+1

    print("use the stairs")
    return
bfs(s,g)

 

위로 올라가거나 아래로 내려가는 부분을 반복문을 사용하면 코드를 줄일 수 있어 아래의 코드로 수정했다.

 

from collections import deque

f,s,g,u,d = map(int,input().split())
visited=[[0 for j in range(2)]for i in range(f+1)]

def bfs(s,g):
    queue = deque()
    queue.append(s)
    visited[s][0]=1
    while queue:
        a = queue.popleft()
        if a==g:
            print(visited[a][1])
            return
        for i in (a+u, a-d):
            if 0<i<=f and visited[i][0] == 0:
                queue.append(i)
                visited[i][0] = 1
                visited[i][1] = visited[a][1]+1
    if visited[g][1] ==0:
        print("use the stairs")
        return
bfs(s,g)

 

풀이도 금방 떠올라서 기분이 좋았다.

매일 공부하는 보람이 있긴 한가보다..

 

처음엔 34%에서 틀렸다고 판정받고, 그 뒤엔 74%에서 틀렸다고 나와서 뭐가 문제인가했더니..

현 위치 - d를 한 값이 0보다 클 때가 아니라 0 이상일 때라고 해서 그게 문제였다.

좀 더 신중히 생각할 필요가 있는 듯