https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 전형적인 bfs의 형태는 아니지만 자주 등장하는 형태입니다. 따라서 이러한 유형을 bfs로 푸는 것에 익숙해져야 합니다. 수빈이가 이동할 수 있는 곳인 (현재 위치 -1, 현재 위치 +1, 현재 위치 * 2)를 bfs의 형태로 탐색을 하여 해결합니다. 다만 주의해야 할 점은 리스트의 범위입니다. 이러한 문제의 경우 인덱스 에러가 쉽게 발생할 수 있으므로 범위에 신경을 써서 문제를 해결해주셔야 합니다. 소스코드는 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
from collections import deque
def bfs(n, k):
q = deque()
q.append(n)
visited[n] = 1
while q:
v = q.popleft()
for i in [v-1, v+1, 2*v]:
if 0 <= i < 100001 and visited[i] == 0:
visited[i] = visited[v] + 1
q.append(i)
if i == k:
return visited[i] - 1
n, k = map(int, input().split())
visited = [0] * 100001
print(bfs(n, k))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 10026번: 적록색약(Python) (0) | 2022.01.15 |
|---|---|
| 백준 알고리즘 4963번: 섬의 개수(Python) (0) | 2022.01.15 |
| 백준 알고리즘 7576번: 토마토(Python) (0) | 2022.01.14 |
| 백준 알고리즘 18870번: 좌표 압축(Python) (0) | 2022.01.12 |
| 백준 알고리즘 11723번: 집합(Python) (0) | 2022.01.10 |