BFS(너비 우선 탐색) - 백준 1697, 5014

1697(숨바꼭질), 5014(스타트링크) 두 문제 모두 큐를 활용한 BFS 방식의 문제다.

이동할 수 있는 거리만큼의 for문을 돌며, 큐에 삽입하고 이동거리를 +1씩 해주며 최종 목적지의 이동거리를 구하였다.

똑같은 위치를 반복해서 방문하게 되면, 필요없는 작업을 하게되어 visited 배열을 통해 한번만 방문하도록 하였다.

 

백준 1697 숨바꼭질

from collections import deque

def bfs(s):
    q = deque([s])
    visited[s]=1
    while q:
        cur = q.popleft()
        if cur == K:
            return count[K]
        for i in (cur-1, cur+1, cur*2):
            if 0 <= i <= 100000 and visited[i]== 0:
                q.append(i)
                visited[i]=1
                count[i] = count[cur] + 1
                
N, K = map(int, input().split())
count = [0]* (100001)
visited= [0] * (100001)
print(bfs(N))

 

백준 5014 스타트링크

from collections import deque

def bfs(s):
    q=deque([s])
    visited[s] = 0
    while q:
        cur = q.popleft()
        if cur == G:
            return count[G]
        for i in (cur+U, cur-D):
            if 0 < i <= F and visited[i] == -1:
                q.append(i)
                count[i] = count[cur] + 1
                visited[i] = 0
    if count[G]==0:
        return "use the stairs"
    
F,S,G,U,D = map(int, input().split())
count = [0] * (F+1)
visited = [-1] * (F+1)
print(bfs(S))