백준 13549 숨바꼭질3

gmlwlswldbs·2022년 1월 16일
0

코딩테스트

목록 보기
117/130
import heapq
INF = int(1e9)

n, k = map(int, input().split())
start = n
d = [INF] * (100001)

q = []
heapq.heappush(q, (0, n))
d[n] = 0
while q:
    dist, now = heapq.heappop(q)
    if d[now] < dist:
        continue
    for y in [now-1, now+1, 2*now]:
        if y > 100000 or y < 0:
            continue
        if y == 2*now:
            cost = dist
        else:
            cost = dist + 1
        if cost < d[y]:
            d[y] = cost
            heapq.heappush(q, (cost, y))
print(d[k]) 

다익스트라 : 그래프는 만들지 않았지만 이동 가능한 곳이 정해져있어서 아래쪽을 약간 변형함. 순간이동은 가중치 0, 아닌 건 가중치 1

from collections import deque

n, k = map(int, input().split())
check = [-1] * (100001)

q = deque()
check[n] = 0
q.append(n)
while q:
    x = q.popleft()
    for y in [x-1, x+1, 2*x]:
        if y < 0 or y > 100000:
            continue
        if y == 2*x:
            tmp = check[x]
        else:
            tmp = check[x] + 1
        if check[y] == -1 or check[y] > tmp:
            check[y] = tmp
            q.append(y)
print(check[k])

bfs : 탐색하는데 만약 check의 값이 크다면 갱신해주었다. 그래서 최단거리를 구함

while q:
    x = q.popleft()
    # 순서를 2*x를 가장 앞에 둬서 가중치를 표현한다
    for y in [2*x, x-1, x+1]:
        if y < 0 or y > 100000:
            continue
        if y == 2*x:
            tmp = check[x]
        else:
            tmp = check[x] + 1
        if check[y] == -1:
            check[y] = tmp
            q.append(y)

while 문을 이렇게 고쳐서 가중치를 표현함. bfs에서 리스트의 순서의 중요성 다시 한번 생각하기

0개의 댓글