13549. 숨바꼭질 3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

이해

• 완전 탐색을 통해 구현할 수 있지만, 이동에 있어 비용이 다르기 때문에 우선순위 큐를 활용한 다익스트라가 더 유리
• 비교를 위해 두 방식 모두 풀이했습니다.

구현

• BFS
  1. 방문했을 때 최소값을 알기 위한 visited 배열 선언(초기화 값은 최댓값인 100,001)
  2. N부터 너비우선 탐색을 통해 탐색
  3. 방문 시 이전 방식보다 가중치가 작다면 최솟값을 변경하면서 탐색
  4. K를 만나면 끝
• Dijkstra(다익스트라) - BFS와 같은 방식으로 진행하지만 차이점 위주로 설명하겠습니다
  1. visited 배열을 방문 표시만 하기 위해 모두 0값으로 초기화
  2. 가중치가 가장 적은 후보군 부터 탐색하며 방문처리
  3. K를 만나면 끝

코드

• BFS

# 13549 숨바꼭질 3
# 42480KB 184ms
import sys
from collections import deque
input = sys.stdin.readline


def solution():
    N, K = map(int, input().split())
    que = deque([(0,N)])
    limit = 100_001
    visited = [limit] * limit
    visited[N] = 0
    while que:
        cost, now = que.popleft()
        if now == K:
            break
        for next in [now-1, now+1, now*2]:
            if 0 <= next < limit:
                if next == now * 2 and visited[next] >= visited[now]:
                    que.append((cost, next))
                    visited[next] =  visited[now]
                
                elif visited[next] >= visited[now]+1:
                    que.append((cost+1, next))
                    visited[next] =  visited[now]+1
    print(visited[K])
    
    return


if __name__ == "__main__":
    solution()

• Dijkstra(다익스트라)

# 13549 숨바꼭질 3
# 34996KB 120ms
import sys, heapq
input = sys.stdin.readline


def solution():
    N, K = map(int, input().split())
    que = []
    limit = 100_001
    heapq.heappush(que, (0, N))
    visited = [0] * limit
    while que:
        cost, now = heapq.heappop(que)
        if now == K:
            print(cost)
            break
        for next in [now-1, now+1, now*2]:
            if 0 <= next < limit and not visited[next]:
                if next == now * 2:
                    heapq.heappush(que, (cost, next))
                    visited[next] = 1
                else:
                    heapq.heappush(que, (cost+1, next))
                    visited[next] = 1
    
    return


if __name__ == "__main__":
    solution()

 

느낀점

• 지난 1697. 숨바꼭질에선 다익스트라로 풀이하는 게 더 느렸지만, 이번엔 더 빨라서 이유를 생각해보니, 가중치가 모두 같을 때와 다를 때, 가중치가 영향을 미처 탐색량이 늘어나면 매번 후보군을 추가하면서 정렬하는 시간보다 더 많이 나간다는 생각이 들었다. 다음부턴 가중치의 여부가 탐색량에 미치는 영향이 많을 때는 반드시 다익스트라를 활용해야겠다.
• BFS 방식으로 풀이할 때, 방문처리만 하면서 탐색하니 틀렸습니다. 가 떠서 풀이한 방식의 차이가 뭔지 생각해보니, 같은 위치를 방문해도 더 짧은 비용을 가진 경로가 있을 때, 탐색을 하지 않아 결과가 달라지는 것으로 생각되었다. 사소한 차이지만 간과하고 넘어가면 바로 틀렸습니다.. 코딩 테스트를 볼 땐 좀 더 주의하도록 하자

유사 문제

2024.01.29 - [Algorithm/BaekJoon Review] - 1697. 숨바꼭질

1697. 숨바꼭질

2024.01.31 - [Algorithm/BaekJoon Review] - 12851. 숨바꼭질 2

12851. 숨바꼭질 2