[백준][BFS][다익스트라] 숨바꼭질 3

 

숨바꼭질 3

 

문제 조건	알고리즘
모든 비용이 같음 (1)	BFS
가중치가 서로 다름	다익스트라
가중치가 0 또는 1	0-1 BFS (덱 사용)

 

• 내 풀이
  • 처음엔 순서대로 진행되는 dp라고 생각했지만 cur-1 처리가 안됨
  • 한 위치에서 x-1, x+1, 2*x 가 다 처리된 뒤에 다음 위치꺼 처리해야하므로 bfs
  • k가 넘어도 다시 돌아올 수 있음 → 조건 범위 맞춰서 100000 으로 크기 설정

from collections import deque
n,k=map(int,input().split())
dp=[float('inf') for _ in range(100001)]

def bfs(cur):
    queue=deque([cur])
    dp[cur]=0

    while queue:
        cur=queue.popleft()

        if cur-1>=0 and dp[cur-1]>dp[cur]+1:
            dp[cur-1]=dp[cur]+1
            queue.append(cur-1)
        if cur + 1 <= 100000 and dp[cur + 1] > dp[cur] + 1:
            dp[cur + 1] = dp[cur] + 1
            queue.append(cur + 1)
        if cur * 2 <= 100000 and dp[cur * 2] > dp[cur]:
            dp[cur * 2] = dp[cur]
            queue.append(cur * 2)

bfs(n)
print(dp[k])

 

 

• 다른 풀이
  • 최단거리지만, 가중치가 0,1인 0-1 BFS 문제
  • 비용이 0이면 appendleft(), 1이면 append()
    •  더 빠르고 깔끔하게 최단 거리 구할 수 있음

from collections import deque

n, k = map(int, input().split())
dp = [float('inf')] * 100001

def bfs(start):
    dq = deque([start])
    dp[start] = 0

    while dq:
        cur = dq.popleft()

        if cur * 2 <= 100000 and dp[cur * 2] > dp[cur]:
            dp[cur * 2] = dp[cur]
            dq.appendleft(cur * 2)

        if cur - 1 >= 0 and dp[cur - 1] > dp[cur] + 1:
            dp[cur - 1] = dp[cur] + 1
            dq.append(cur - 1)

        if cur + 1 <= 100000 and dp[cur + 1] > dp[cur] + 1:
            dp[cur + 1] = dp[cur] + 1
            dq.append(cur + 1)

bfs(n)
print(dp[k])

 

 

• 다른 풀이 
  • 가중치가 있는 최단거리 문제 => 다익스트라
  • 우선순위 큐(heap)

항목	0-1 BFS	다익스트라
사용 조건	가중치가 0 또는 1	가중치가 0 이상 아무 값이나 가능
자료구조	deque (앞뒤로 넣기)	우선순위 큐 (heapq)
주요 전략	0이면 앞에 넣고, 1이면 뒤에 넣는다	항상 최단 거리 기준으로 정렬

import heapq

n, k = map(int, input().split())
dp = [float('inf')] * 100001

def dijkstra(start):
    hq = []
    heapq.heappush(hq, (0, start))  # (비용, 위치)
    dp[start] = 0

    while hq:
        cost, cur = heapq.heappop(hq)

        if dp[cur] < cost:
            continue

        if cur * 2 <= 100000 and dp[cur * 2] > cost:
            dp[cur * 2] = cost
            heapq.heappush(hq, (cost, cur * 2))

        if cur + 1 <= 100000 and dp[cur + 1] > cost + 1:
            dp[cur + 1] = cost + 1
            heapq.heappush(hq, (cost + 1, cur + 1))

        if cur - 1 >= 0 and dp[cur - 1] > cost + 1:
            dp[cur - 1] = cost + 1
            heapq.heappush(hq, (cost + 1, cur - 1))

dijkstra(n)
print(dp[k])

import heapq

n, k = map(int, input().split())
dp = [float('inf')] * 100001
dp[n] = 0

hq = [(0, n)]
while hq:
    cost, cur = heapq.heappop(hq)

    if cur == k:
        break

    for next_pos, next_cost in [(cur * 2, 0), (cur - 1, 1), (cur + 1, 1)]:
        if 0 <= next_pos <= 100000 and dp[next_pos] > cost + next_cost:
            dp[next_pos] = cost + next_cost
            heapq.heappush(hq, (dp[next_pos], next_pos))

print(dp[k])