[python]🔥13549번 숨바꼭질 3, 다양한 풀이

우선 나의 풀이는 다익스트라가 아닌 bfs로 풀이하였다.

그러나 우선순위큐나 appendleft순서로 풀이를 하지 않고, 

visit변수를 응용해서 풀이하였다.

 

일반적인 bfs풀이는 목적지에 도달하면 바로 종료하지만(가장 먼저 도달한 것이 최단거리이기 때문에)

가중치가 있어 해당되지 않는다.

 

따라서 나는 visit값을 방문 값으로 설정하여, visit값보다 높을 경우 방문 불가하지만(이미 방문했던 적이 있는 노드값이 최적이기에) visit값 보다 작은 값이 나올시 재방문이 가능하도록 하였다.

 

나의 풀이

from collections import deque
start, end = map(int,input().split())
mmx = 1000000
visit = [mmx for i in range(mmx+2)]
que = deque()
que.append((start,0,0))
if start==end:
    print(0)
    exit(0)
while que:
    cur = que.popleft()
    for i in [1,-1,2]:   #한칸씩 이동 or 2배 순간이동하기
        if i!=2:		#한칸씩 이동할 때
            if 0<=cur[0]+i<mmx+1 and visit[cur[0]+i]>cur[1]+1-cur[2]: #범위 안에 있고, 방문값이 기존값보다 작을때(더 짧은 길일때!)
                if cur[0]+i == end:
                    visit[cur[0]+i] = cur[1]+1-cur[2]
                    continue
                visit[cur[0]+i] = cur[1]+1-cur[2]
                que.append((cur[0]+i,cur[1]+1,cur[2]))
        else:		#2배 순간이동할 때
            if 0<=cur[0]*2<mmx+1 and visit[cur[0]*2]>cur[1]-cur[2]: #범위 안에 있고, 방문값이 기존값보다 작을때(더 짧은 길일때!)
                if cur[0]*2 == end:
                    visit[cur[0]*2] = cur[1]-cur[2]
                    continue
                que.append((cur[0]*2,cur[1]+1,cur[2]+1))
                visit[cur[0]*2] = cur[1]-cur[2]
print(visit[end])

 

 

1번 bfs appendleft 풀이

그러나 사람들의 풀이를  찾아보니 더 효율적이고 간단한 방식들이 있었다.

우선 순서를 신경을 써서 한 풀이이다.

2배 이동한것이 0초 걸리기에, 무조건 더 효율적인 길이다.

가장 최단거리는 이 2배 간 길에서 파생되서 나오기에, 2배한 정점을 appendleft로 먼저 popleft되면 가장 먼저 뽑히게된다.

from collections import deque

n, k = map(int, input().split())
graph = [0] * (100000 + 1)

def bfs(x):
    deq = deque([x])
    
    while deq:
        x = deq.popleft()
        
        if x == k:
            return graph[x]
        
        for i in (x - 1, x + 1, x * 2):
            if 0 < i <= 100000 and not graph[i] and i == x * 2:
                graph[i] = graph[x]
                deq.appendleft(i)
                    
            elif 0 <= i <= 100000 and not graph[i]:
                graph[i] = graph[x] + 1
                deq.append(i)

print(bfs(n))

2번 priority queue를 이용한 bfs 풀이

1번 방법을 우선순위 큐를 사용하여 풀이

from heapq import heappush,heappop

n, k = map(int, input().split())
graph = [0] * (100000 + 1)

def bfs(x):
    deq = []
    heappush(deq,(0,x))
    
    while deq:
        x = heappop(deq)
        if x[1] == k:
            return graph[x[1]]
        
        for i in (x[1] - 1, x[1] + 1, x[1] * 2):
            if 0 < i <= 100000 and not graph[i] and i == x[1] * 2:
                graph[i] = graph[x[1]]
                heappush(deq,(graph[i],i))
                    
            elif 0 <= i <= 100000 and not graph[i]:
                graph[i] = graph[x[1]] + 1
                heappush(deq,(graph[i],i))

print(bfs(n))

3번 다익스트라

보통의 다익스트라 처럼 풀이를 하지만, 차이점은 그래프 모양들이 1부터 100000까지 이미 노드들이 +1,-1,*2의 거리만큼의 노드들과 이어져있다는 것이다.

 

from heapq import heappush,heappop
stg = [1e9 for i in range(100001)]   #초기 거리값 무한대로 설정
start,end = map(int,input().split())
stg[start] = 0
que = [(0,start)]
while que:
    curlen,curx = heappop(que)
    if curx == end:   #목적지 도착
        break
    for i in [curx+1,curx-1,curx*2]:    #그래프 이동
        if 0<=i<100001:
            if i!=curx*2:    #가중치 1일때
                if stg[i]>curlen+1:
                    stg[i] = curlen+1
                    heappush(que,(stg[i],i))
            else:       #가중치 0일때
                if stg[i]>curlen:
                    stg[i] = curlen
                    heappush(que,(stg[i],i))
print(curlen)