13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 BFS를 이용하면 해결할 수 있는 문제였습니다. 보통 BFS 문제의 경우 이차원 리스트 혹은 이차원 배열에서 특정 지점에서 다른 지점으로 퍼져나가는 형식으로 탐색하는 것인데 특이하게 이 문제의 경우 일차원 리스트상에서 해결해야 하기 때문에 처음에는 생각하기가 조금 어려웠던 문제였습니다.
먼저 문제의 예시를 살펴보도록 하겠습니다.
5의 위치에서 시작하여 17까지 가야합니다. 시간이 걸리지 않는 순간이동의 방식으로 현재 위치 * 2 한 지점으로 이동할 수 있습니다. 또는 시간이 1초 걸려서 현재 위치의 좌측 위치 혹은 우측 위치로 이동할 수 있습니다.
이를 너비 우선이 방식으로 큐에 넣어주고 차례 차례 탐색해 나갑니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
n, m = map(int, input().split())
max = 100001
visited = [0] * max
move = [-1, 1]
def bfs():
q = deque()
q.append(n)
count = 0
visited[n] = 1
if 2*n < max and not visited[2*n]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우 순간이동으로 탐색
visited[2*n] = 1
q.append(2*n)
if visited[m] != 0: # 도착점인 경우
print(visited[m] - 1)
return
while q:
pos = q.popleft()
if visited[m] != 0: # 도착점인 경우
print(visited[m] - 1)
return
if 2*pos < max and not visited[2*pos]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우
visited[2*pos] = visited[pos] # 순간이동으로 탐색
q.append(2*pos)
for i in range(2): # 시간을 1초 소비하며 좌, 우를 탐색하는 경우
npos = pos + move[i]
if 0 <= npos < max:
if not visited[npos]:
visited[npos] = visited[pos] + 1
q.append(npos)
bfs()
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1010번: 다리 놓기 (Python) (0) | 2021.12.27 |
|---|---|
| 백준 알고리즘 1463번: 1로 만들기 (Python) (0) | 2021.12.27 |
| 백준 알고리즘 1504: 특정한 최단 경로(Python) (0) | 2021.02.23 |
| 백준 알고리즘 1068: 트리(Python) (0) | 2021.02.21 |
| 백준 알고리즘 1074: Z(Python) (0) | 2021.02.20 |