[ 탐색 ] 백준 13549 숨박꼭질 3

문제 링크

13549번: 숨바꼭질 3

 

💡문제 분석 요약

탐색 알고리즘 중 하나인 BFS를 활용하여 문제를 풀이하면 쉽다.

DFS를 떠올릴 수 있으나, 이 문제에서 DFS은 적절한 방법이 될 수 없다. 효율성이 떨어지기 때문이다.
- 최단 경로 찾기의 비효율성: 현재의 문제는 가장 빠른 시간을 찾아야한다. 하지만 DFS는 깊이 우선 탐색의 특성으로, 최적이 아닌 경로를 더 오랫동안 탐색하게 될 수 있어 적합하지 않다.

 

 

💡알고리즘 설계

BFS 알고리즘을 만들기 위해, Queue 자료구조를 사용하며, 위치 정보를 Queue에 담고, 시간에 따라 해당 값을 추가(append), 추출(pop)하면 된다.

• 시간에 따라 이동이 달라지므로, 순간이동(0초)의 경우 가장 앞에 위치정보를 추가하고, 이동(1초)의 경우 가장 뒤에 값을 추가한다.

 

💡코드

from collections import deque

def bfs(N, K):
    visited = [False] * 100001
    
    queue = deque([(N, 0)])  
    visited[N] = True
    
    while queue:
        current_pos, current_time = queue.popleft()
        
        if current_pos == K:
            return current_time
       
        for next_pos in (current_pos - 1, current_pos + 1, current_pos * 2):
            if 0 <= next_pos <= 100000 and not visited[next_pos]:
                visited[next_pos] = True
                if next_pos == current_pos * 2:
                    queue.appendleft((next_pos, current_time))
                else:
                    queue.append((next_pos, current_time + 1))
    return -1

N, K = map(int, input().split())

print(bfs(N, K))

 

💡시간복잡도

BFS(Breadth-First Search) 알고리즘의 시간 복잡도는 O(N)으로 선형 시간이 소요된다. 그리고 N은 0 <= N <=100,000 이며 시간 및 메모리 제한에 문제가 없다.

• queue의 추가(apppend)와 추출(pop)의 시간복잡도는 O(1)이다.

 

💡 느낀점 or 기억할정보

탐색알고리즘을 사용할 때면, BFS, DFS를 고려하게되는데, 나는 구현이 BFS가 편리하여 BFS를 더 선호하곤했다. 하지만 이번 문제를 풀이해보면서 BFS가 적합할 때와 DFS가 적합한 때를 고려해서 선택해야함을 알 수 있었다. 구현 편의성 보다는 모두 구현할 수 있도록 연습을 하고, 상황에 알맞은 알고리즘을 사용할수 있도록 노력해야겠다.