[python] 13549 - 숨바꼭질 3

13549번: 숨바꼭질 3 (acmicpc.net)

13549번: 숨바꼭질 3

 

이번 문제는 bfs와 다익스트라 두 가지 방법으로 풀이할 수 있다.

전에 bfs 문제를 풀 때 다루었던 문제랑 똑같은게 아닌가? 했는데

이 문제에서는 가중치를 고려해야한다.

 

그래서 전에 풀었던 bfs 방식에서 가중치를 고려하여 살짝 변형하여 풀고

최근에 학습한 다익스트라로도 코드를 짜 보았다.

 

 

[BFS]

import sys
from collections import deque

# 13549 bfs

input = sys.stdin.readline

n,k = map(int, input().split())
lst=[0]*100001

def bfs(n, k):
    q = deque()
    q.append(n)
    lst[n] = 1
    
    while q:
        start = q.popleft()
        
        if start == k:
            return lst[k]
            
        for i in (start*2,start-1,start+1):
            if i >=0 and i <= 100000 and lst[i] == 0:
                if i == start*2:
                    lst[i] = lst[start]
                    q.appendleft(i)
                else:
                    lst[i] = lst[start]+1
                    q.append(i)
                    

print(bfs(n,k)-1)

가중치를 고려해야 하므로 순간이동을 할 때(가중치가 0일 때)를 항상 먼저 탐색해야 한다.

따라서 appendleft()를 사용하여 덱의 가장 앞에 넣어주어 우선 탐색을 하도록 하였다.

처음 최대값 고려를 하지못해 index에러가 났고

그 다음에는 처음 시작 값 n의 거리값을 바꿔주지않아 시간 초과가 걸렸다.

두 가지를 해결하니 무사히 통과했다.

 

[dijkstra]

import sys
import heapq

# 13549 dijkstra
input = sys.stdin.readline
INF = int(1e9)


def dijkstra(n,k):
    dist=[INF]*100001
    q = []
    dist[n] = 0
    heapq.heappush(q, (0,n))
    
    while q:
        weight, curr = heapq.heappop(q)
        
        if curr == k:
            return dist[k]
        if dist[curr] < weight:
            continue
        
        for cost, next in [(0, curr*2), (1, curr+1), (1, curr-1)]:
            next_w = weight + cost
            if 0<= next <= 100000 and next_w < dist[next]:
                dist[next] = next_w
                heapq.heappush(q, (next_w, next))
                        
n,k = map(int, input().split())
print(dijkstra(n,k))

 bfs와 비슷한데 deque 대신 heapq를 사용하여 가중치가 가장 작은 것 부터 탐색한다.