[백준] 1697번(python 파이썬)

https://www.acmicpc.net/problem/1697

 

---

수빈이가 다음 장소로 갈 수 있는 경우의 수는 3가지 이다.

3가지 경우의 수를 방문하면서 동생의 위치와 같을 때 까지 탐색을 한다.

현재 인덱스에서 다음 방문할 3개의 경우의 수를 모두 방문하여 동생의 위치와 같은 경우를 찾아야 하기 때문에 BFS를 사용한다.

visited = [] 1차원 배열을 사용하여 해결할 수 있다.

처음 수빈이가 있는 인덱스를 방문처리(1로 지정)한다.

현재 노드에서 다음 3가지 인덱스를 방문한다. 여기서 방문처리는 (다음 노드 = 현재 노드 + 1) 로 나타 낼 수 있다.

인덱스가 동생의 위치와 같아질 경우 끝나게 되는데 이때 동생의 인덱스 까지 최소 몇번만에 도달하였는지 동생이 위치한 인덱스의 원소(다음 노드 = 현재 노드 + 1)로 알 수있다.

처음에 수빈이가 있는 인덱스의 원소값을 1로 시작하였으므로 마지막에 1을 빼준다.

 

---

from collections import deque

n, k = map(int, input().split())
dx = [-1, 1, 2]
visited = [0] * 100001
visited[n] = 1

def Bfs():
    queue = deque([n])

    while queue:
        cur_x = queue.popleft()
        if cur_x == k:
            return visited[k]
        for i in range(3):
            if i == 2:
                next_x = cur_x * dx[i]
            else:
                next_x = cur_x + dx[i]

            if 0 <= next_x <= 100000 and visited[next_x] == 0:
                queue.append(next_x)
                visited[next_x] = visited[cur_x] + 1

print(Bfs() - 1)