백준 13549번 숨바꼭질 3 파이썬
문제
입력 , 출력
solution
import sys
from collections import deque
input = sys.stdin.readline
Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
while dq:
a = dq.popleft()
if a == m:
break
if a * 2 < Max and dis[a * 2] == -1:
dq.appendleft(a * 2)
dis[a * 2] = dis[a]
if a + 1 < Max and dis[a + 1] == -1:
dq.append(a + 1)
dis[a + 1] = dis[a] + 1
if a - 1 >= 0 and dis[a - 1] == -1:
dq.append(a - 1)
dis[a - 1] = dis[a] + 1
print(dis[m])
설명
키포인트
- 현재 위치에서 *2 로 이동하는것은 비용이 0 이다.
- 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다.
- 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다.
import sys
from collections import deque
input = sys.stdin.readline
Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
while dq:
a = dq.popleft()
if a == m:
break
if a * 2 < Max and dis[a * 2] == -1:
dq.appendleft(a * 2)
dis[a * 2] = dis[a]
if a + 1 < Max and dis[a + 1] == -1:
dq.append(a + 1)
dis[a + 1] = dis[a] + 1
if a - 1 >= 0 and dis[a - 1] == -1:
dq.append(a - 1)
dis[a - 1] = dis[a] + 1
print(dis[m])
키포인트
- 현재 위치에서 *2 로 이동하는것은 비용이 0 이다.
- 1번에 의해서 큐에 제일 앞에 넣어줘서 *2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다.
- 그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다.
제일 중요한건 *2로 이동하는 가중치가 0 이기 때문에 체크를 할 경우에
큐에 가장 앞에 넣어주는게 제일 중요한 키포인트
Author And Source
이 문제에 관하여(백준 13549번 숨바꼭질 3 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@slbin-park/백준-13549번-숨바꼭질-3-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)