공부 기록장
백준 13549. 숨바꼭질3 본문
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
코드
from collections import deque
n, k = map(int, input().split())
q = deque()
q.append(n)
visited = [-1 for _ in range(100001)]
visited[n] = 0
while q:
s = q.popleft()
if s == k:
print(visited[s])
break
if 0 <= s-1 < 100001 and visited[s-1] == -1:
visited[s-1] = visited[s] + 1
q.append(s-1)
if 0 < s*2 < 100001 and visited[s*2] == -1:
visited[s*2] = visited[s]
q.appendleft(s*2) # 2*s 가 다른 연산보다 더 높은 우선순위를 가지기 위함
if 0 <= s+1 < 100001 and visited[s+1] == -1:
visited[s+1] = visited[s] + 1
q.append(s+1)
숨바꼭질 문제에서 2*X 이동 가중치가 0으로 바뀐 것 말고는 동일한 문제이다.
다른 분들의 코드를 참고했다.
주요 아이디어는 deque의 appendleft를 통해
가중치가 0인 2*X 연산을
다른 연산들 보다 우선순위가 높게 해야 풀리는 문제였다.
참고 자료
'코딩 테스트 > 백준 문제 풀이' 카테고리의 다른 글
| 백준 1753. 최단 경로 (0) | 2024.01.23 |
|---|---|
| 백준 11404. 플로이드 (0) | 2024.01.23 |
| 백준 2812. 크게 만들기 (0) | 2024.01.23 |
| 백준 2138. 전구와 스위치 (0) | 2024.01.22 |
| 백준 13975. 파일 합치기 3 (0) | 2024.01.22 |