[BOJ] 13913. 숨바꼭질 4(🥇, BFS)

문제

풀이

최단거리 구하기 = bfs 풀이

풀이1(시간초과)

무식하게 모든 이동 루트들을 큐에 같이 저장했다. 메모리가 터지든 저장하다 시간이 터지든 둘 중 하나일거라고 생각했는데 시간이 터졌다

# 숨바꼭질 4

def bfs(N, K):
    queue = [(N, [N])]

    visited[N] = 1
    while queue:
        s, route = queue.pop(0)
        
        # print(route, s, K)
        if s == K:
            return route
        
        t = visited[s]
        if -1<s-1 and visited[s-1] == -1:
            queue.append((s-1, route+[s-1]))
            visited[s-1] = t+1
        if s+1<100001 and visited[s+1] == -1:
            queue.append((s+1, route+[s+1]))
            visited[s+1] = t+1
        if s*2<100001 and visited[s*2] == -1:
            queue.append((s*2, route+[2*s]))
            visited[s*2] = t+1


N, K = map(int, input().split())
visited = [-1]*100001

route = bfs(N, K)
print(visited[K]-1)
print(*route)

풀이2

근데 애초에 시간이 안 터져도 위의 풀이는 틀릴 수 밖에 없었다.
이 블로그를 참조해서 풀어도 계속 시간초과가 나길래 이유를 찾아봤더니

처음부터 visited를 0으로 초기화하면 안 되는거였다.

블로그의 풀이는 요약하면

1. visited 배열에는 직전 위치를 기록한다
2. 큐에는 이동하는 시간을 기록한다

인데, 위의 내 풀이와 완전 반대다. 나는 visited배열에 시간을, 큐에 이동 위치를 기록했는데 큐에 시간을 기록하면 시간은 계속 숫자하나로 기록되지만 이동 위치를 기록하면 리스트가 무한대로 늘어날 수 있기 때문에 비효율적이다.

# 168ms

from collections import deque

N, K = map(int, input().split())
path, visited = [], [-1]*100001

def bfs(start, target):
    queue = deque()
    queue.append((start, 0))

    # visited 배열에 이전의 위치를 기록
    # queue에 이동한 시간(cur_time) 기록

    # target을 발견하면 이전으로 한칸씩 이동하다가 
    # 최초 지점(visited가 start인 곳)을 만나면 종료
    visited[start] = start
    while queue:
        now, move_time = queue.popleft()

        if now == target:
            cur = now

            # visited[cur]에는 cur에 오기 직전의 위치가 기록되어 있음
            # 출발점에 도착하면 출발점은 path에 추가되지 않고 종료되므로 따로 추가해줘야 함
            while cur != start:
                path.append(cur)
                cur = visited[cur]
            path.append(start)
            return move_time
        
        if now+1 < 100001 and visited[now+1] == -1:
            visited[now+1] = now
            queue.append((now+1, move_time+1))
        
        if now-1 > -1 and visited[now-1] == -1:
            visited[now-1] = now
            queue.append((now-1, move_time+1))

        if now*2 < 100001 and visited[2*now] == -1:
            visited[2*now] = now
            queue.append((2*now, move_time+1))

print(bfs(N, K))
print(*path[::-1])