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, 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.244
(코딩 테스트) 백준 숨바꼭질 (1697) Python
https://www.acmicpc.net/problem/1697 1697호 숨바꼭질 수빈이 여동생과 숨바꼭질을 하고 있다. 수빈은 현재 포인트 N(0 ≤ N ≤ 100,000)에 있고, 동생은 포인트 K(0 ≤ K ≤ 100,000)에 있다. 수빈이 걷거나 순간이동
my-develop-note.tistory.com
컬렉션의 deque를 사용하여 bfs를 구현하는 것은 숨바꼭질을 하는 것과 같습니다(1697).
그러나 검사 논리(2*x, x-1, x+1)는 약간 다릅니다.
2*x의 경우 0초가 걸리고 그렇지 않으면 1초가 걸립니다.
그러나 순회 순서가 (2*x, x-1, x+1)인 경우에만 문제가 통과되었습니다.
자세한 내용은 이 기사를 확인하십시오.
기사 읽기 – (Python) 무엇이 다른가요? (반드시 답변 부탁드립니다.)
댓글을 달려면 로그인해야 합니다.
www.acmicpc.net
원래 Dijkstra의 알고리즘은 현재 거리보다 짧은 거리가 발견되면 업데이트되지만 내 논리는 항상 방문한 것으로 간주합니다. 그렇기 때문에 순서가 맞지 않으면 문제를 통과하지 못하고, 간단한 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를 먼저 찾아야 하기 때문에 답이 높을 가능성이 높다.