[백준] 5014 스타트링크 (실버1) / BFS

문제요약

나의 코드 및 설명

from collections import deque

def bfs(start, end):
    queue = deque()
    queue.append(start) #현재 좌표 값 큐에 추가
    visited[start] = 1 #현재 좌표 방문처리
    while queue:
        now = queue.popleft()
        if now == end: #목표 층에 도달하면
            return visited[now]-1 #룩업테이블의 현재 좌표 값 -1 
        for i in (now+u, now-d): #위로 가거나 아래로 가는 두 가지
            if 1<=i<=f and visited[i] == 0: #1층부터 옥상까지의 범위 & 아직 방문 안한 좌표
                visited[i] = visited[now] + 1 #다음 좌표 값 = 현재 좌표 값 + 1
                queue.append(i) #다음 좌표 값 큐에 추가
    return -1 #여기까지 온다면 목표 층에 도달 못한 것

f,s,g,u,d = map(int,input().split())
visited = [0] * 1000001

ans = bfs(s,g)
if ans == -1:
    print("use the stairs")
else:
    print(ans)

피드백

처음엔 DFS 멀티트리나 이진트리로 풀려다가 실패했다. BFS로 풀어보니 생각보다 간단히 풀 수 있었다. 여기서 주의할 점은 룩업 테이블을 활용해야 편하다는 점이다. 처음에는 count 전역 변수를 통해 큐에 좌표를 넣어줄 때마다 count 값을 1씩 증가시키는 방식으로 풀려고 했으나 값이 예제 출력값보다 크게 나왔다. 파이썬 튜터를 통해 이해할 수 있었는데, now의 다음 좌표(올라가거나 내려가거나)로 가지 못하면 count 값을 증가시키면 안되는데, 다음 값을 큐에 넣지 않아도 count 값을 증가시켜버린 탓이었다. 룩업테이블을 활용하여 다음 좌표를 큐에 넣어줄 때 현재 좌표에 저장된 값에 1을 더한 값으로 방문처리 해주었더니 문제를 해결할 수 있었다.

다음 좌표가 이미 방문처리 되어서 방문하지 못하는데 count하게 된다.