[코딩테스트] 백준 숨바꼭질3(13549) 파이썬(Python)

 

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

13549번: 숨바꼭질 3

from collections import deque

n, k = map(int, input().split())

q = deque()
q.append((n, 0))
visited = set()
visited.add(n)
while q:
    x, d = q.popleft()
    if x == k:
        break
    for next_x in [2*x, x-1, x+1]:
        if next_x not in visited and 0 <= next_x <= 100000:
            visited.add(next_x)
            if next_x != 2*x:
                q.append([next_x, d+1])
            else:
                q.append([next_x, d])
        
print(d)

예전에 풀었던 숨바꼭질(1697) 문제와 유사한 문제입니다.

https://my-develop-note.tistory.com/244

[코딩테스트] 백준 숨바꼭질(1697) 파이썬(Python)

collections의 deque를 이용해서 bfs를 구현한 것은 숨바꼭질(1697)과 마찬가지 입니다.

 

하지만 [2*x, x-1, x+1]를 확인하는 로직이 조금 다릅니다.

 

2*x 일때는 0초가 걸리고, 나머지는 동일하게 1초가 걸립니다.

하지만 순회 순서를 [2*x, x-1, x+1]로 해야만 문제가 통과가 되었습니다.

 

해당 글을 확인하면 좀 더 자세히 알 수 있습니다.

글 읽기 - [파이썬] 무엇이 다른가요? (꼭 답변 부탁드립니다 ㅠㅠ)

원래 다익스트라 알고리즘은 현재 거리보다 더 짧은 거리를 찾았을 때 갱신이되는데 저의 로직은 항상 visited로 방문처리를 합니다. 그렇기 때문에 순서를 맞추지 않으면 문제를 통과하지 못하는 것이고, 단순 BFS로 우연히도 항상 정답을 찾을 수 있을 뿐이라고 합니다.

 

[2*x, x-1, x+1]의 순서에 상관없이 문제를 해결하려면 2*x일 경우에만 q에 가장 앞부분에 넣어주면 통과하게 됩니다.

from collections import deque

n, k = map(int, input().split())

q = deque()
q.append((n, 0))
visited = set()
visited.add(n)
while q:
    x, d = q.popleft()
    if x == k:
        break
    for next_x in [x-1, x+1, 2*x]:
        if next_x not in visited and 0 <= next_x <= 100000:
            visited.add(next_x)
            if next_x == 2*x:
                q.appendleft([next_x, d])
            else:
                q.append([next_x, d+1])
                
        
print(d)

가장 빠른 시간을 찾아야 하기 때문에 시간이 증가하지 않는 2*x를 먼저 찾아야 정답에 가능성이 높기 때문이 아닐까 생각합니다.