www.acmicpc.net/problem/13549

 

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 = [-11]
 
def bfs():
    q = deque()
    q.append(n)
    count = 0
    visited[n] = 1
    if 2*< 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

 

+ Recent posts