[백준] 13549번: 숨바꼭질 3 - python

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

13549번: 숨바꼭질 3

 

아이디어

 

BFS로 탐색을 하면서 순간이동할때는 가중치를 더하지말고, 이동할때는 더해서 dis 리스트에 계속해서 상태트리형식으로 뻗어나가는 형태를 생각하고 문제를 풀었다. 그러던중 신기한 현상이 발생했다.

 

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

ch = [0] * (100001)
dis = [0] * (100001)

ch[n] = 1
dis[n] = 0

dq = deque([n])

while dq:
    now = dq.popleft()
    if now == m:
        break

    for next in (now*2, now+1, now-1):
        if 0<=next<100001:
            if ch[next]==0:
                ch[next] = 1
                if next == now * 2:
                    dis[next] += dis[now]
                else:
                    dis[next] += dis[now] + 1
                dq.append(next)
print(dis[m])

문제는 맞혔으나,

 

(now*2, now+1, now-1)

 

의 순서를 다르게 할때마다 맞고 틀리고가 달리졌기 때문이다. 그래서 질문게시판에서 이유를 찾아봤는데..

 

https://www.acmicpc.net/board/view/38887

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

 

원래의 문제 의도는 다익스트타를 사용하는게 맞는 문제였던 것이다. 이번 문제는 우연찮게 맞혔으나 간선의 가중치가 다른 보편적인 문제는 이런식으로 안풀린다는 것이었다. 다음부턴 공부를 하고 풀어봐야겠다..ㅎ

 

완성