[백준]13549 숨바꼭질3 파이썬 python

문제링크

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

13549번: 숨바꼭질 3

코드

import sys
input = sys.stdin.readline
from collections import deque
 
MAX = 200001
n, k = map(int, input().split())
visited = [-1 for _ in range(MAX)] 
 
def bfs(n,k):
    dq = deque()
    visited[n]=0
    dq.append(n)
    while dq:
        x = dq.popleft()
        # 타겟과 일치
        if x == k:
            print(visited[k])
            break
        lst = [2*x,x-1,x+1]
        for i, nx in enumerate (lst):
            if 0<=nx<MAX and visited[nx]==-1: #아직 한번도 방문 X
                if i!=0:
                    visited[nx] = visited[x]+1 #Action 1&2 (가중치1)
                    dq.append(nx)
                else:
                    visited[nx] = visited[x] #Action 3 (가중치0)
                    dq.appendleft(nx)
bfs(n,k)
 
 

 

Point

- action별로 가중치가 다르다. 가중치가 다른데 같은 queue에서 처리해도 될까?? 

1) queue를 2개로 나누어서 처리해도 된다.

2) appendleft를 사용한다.

2배로 움직이는 action은 가중치가 0이기 때문에 appendleft를 사용하여 먼저 queue에 넣는다.

그리고 visited 배열 업데이트 할 때에도 next = now +1 이 아닌 next = now를 적용한다.

 

- lst = [x-1,x+1,2*x] 순서로 하면 오답이다!!!!!

코드 20줄에서 lst = [x-1,x+1,2*x] 순서로 하면 오답 처리가 된다.

이 부분을 찾아내느라 굉장히 많은 시간이 걸렸다... ! :( 

[x-1,x+1,2*x] 순서로 하면  n=1,k=2 일 때 ans = 0이 정답인데, ans = 1로 도출한다.

순간이동(2*x) 가중치가 더 적기 때문에 큐에 먼저 들어갈 수 있도록 해야한다!!!!!!!

 

.