https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
마찬가지로 bfs로 해결하였다.
경우의 수를 다 해보는 방식으로 조금 더 발전시켜서 점화식을 찾는다면 dp로 풀 수 있을 것 같다.
from collections import deque
start, end = map(int,input().split());
arr = [0 for i in range(0,100001)]
q = deque([])
q.append([start,0])
arr[start] = 1
while q:
# print(q)
x, cnt = q.popleft();
arr[x] = 1
if x == end:
answer = cnt
break
if x > 0 and arr[x-1] == 0:
q.append([x - 1, cnt+1]);
arr[x-1] = 1
if x < 100000 and arr[x + 1] == 0:
q.append([x + 1, cnt+1]);
arr[x+1] = 1
if x <= 50000 and arr[x *2] == 0:
q.append([x * 2, cnt+1]);
arr[x*2] = 1
print(answer)'알고리즘' 카테고리의 다른 글
| [백준] 13460: 구슬 탈출 2 (0) | 2022.04.29 |
|---|---|
| [백준] 5014번: 스타트링크 (0) | 2022.03.22 |
| [백준] 2644번: 촌수계산 (0) | 2022.03.22 |
| [백준] 2667번: 단지번호붙이기 (0) | 2022.02.02 |
| [백준] 7576번: 토마토 (0) | 2022.02.02 |