[백준] 12851번 숨바꼭질 2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4
2

내 코드

메모리 초과

from collections import deque

def bfs(start):
    if start >= K:
        return start - K, 1

    queue = deque([(start, 0)])
    visited = {start}  # set
    answer = {'step': 0, 'count': 0}

    while queue:
        for _ in range(len(queue)):
            current, step = queue.popleft()

            # 3가지 방법 이동
            for move in (2 * current, current + 1, current - 1):

                # K와 만나면
                if move == K:
                    if answer['step'] == 0:
                        answer['step'] = step + 1
                    answer['count'] += 1

                # K와 안 만나면
                elif move not in visited:
                    queue.append((move, step + 1))
                    visited.add(move)  # 방문처리

        if answer['count'] != 0:
            return answer['step'], answer['count']

N, K = map(int, input().split())

print(*bfs(N), sep='\\n')
# 메모리 초과

내 코드 수정

chatGPT가 직접 푼 코드보다 시간 3배 더 걸린다.

from collections import deque

def bfs(start):
    if start >= K:
        return start - K, 1  # 수빈이가 K보다 앞에 있으면 단순히 -1씩 이동

    max_limit = 100000  # 탐색 범위 제한
    visited = [0] * (max_limit + 1)  # 방문 시간 기록 (0은 미방문)
    queue = deque([start])
    visited[start] = 1  # 시작점 방문 처리 (1은 시작 시간)

    count = 0  # 동생을 찾는 방법의 수
    while queue:
        current = queue.popleft()

        # 동생을 찾은 경우
        if current == K:
            count += 1  # 방법 수 증가
            continue  # 동생을 찾았으므로 추가 탐색 생략

        # BFS 탐색 (X-1, X+1, 2*X)
        for move in (current - 1, current + 1, current * 2):
            if 0 <= move <= max_limit:
                # 아직 방문하지 않았거나, 같은 시간에 방문할 수 있는 경우
                if visited[move] == 0 or visited[move] == visited[current] + 1:
                    visited[move] = visited[current] + 1  # 시간 갱신
                    queue.append(move)

    # 가장 빠른 시간과 해당 경로 수 반환
    return visited[K] - 1, count

N, K = map(int, input().split())
print(*bfs(N), sep='\\n')

chatGPT

BFS 해결 방법

1. 큐를 활용: 현재 위치와 경과 시간을 저장.
2. 방문 처리: 방문 배열(visited)을 만들어 중복 탐색 방지. 단, 다른 경로로 동일한 시간에 방문할 수 있는 경우를 고려해 경로의 수를 누적.
3. 탐색 종료 조건: K에 처음 도달했을 때 경과 시간을 저장하고, 이후 동일 시간에 도달한 경우만 경로 수를 증가.

---

풀이 코드

from collections import deque

def find_shortest_time_and_paths(N, K):
    MAX = min(max(N, K) * 2, 100001)  # 범위 제한
    visited = [-1] * MAX  # 방문 여부 및 도달 시간을 저장 (-1: 미방문)
    ways = [0] * MAX  # 경로 수 저장

    queue = deque([N])  # 시작 위치
    visited[N] = 0  # 시작 위치 시간 0
    ways[N] = 1  # 시작 위치 경로 수 1

    while queue:
        current = queue.popleft()

        for next_pos in (current - 1, current + 1, current * 2):  # 가능한 이동
            if 0 <= next_pos < MAX:
                # 처음 방문하는 경우
                if visited[next_pos] == -1:
                    visited[next_pos] = visited[current] + 1  # 시간 갱신
                    ways[next_pos] = ways[current]  # 경로 수 복사
                    queue.append(next_pos)
                # 같은 시간에 도달한 경우
                elif visited[next_pos] == visited[current] + 1:
                    ways[next_pos] += ways[current]  # 경로 수 누적

    return visited[K], ways[K]

# 입력
N, K = map(int, input().split())
time, path_count = find_shortest_time_and_paths(N, K)

# 출력
print(time)
print(path_count)

코드 설명

1. 초기화:
   • visited: 각 위치에 도달한 최소 시간을 기록.
   • ways: 해당 위치에 도달할 수 있는 경로의 수를 저장.
2. BFS 탐색:
   • 현재 위치에서 가능한 다음 위치로 이동.
   • 방문하지 않은 위치라면 시간을 갱신하고 경로 수를 기록.
   • 동일한 시간에 방문할 수 있다면 경로 수를 누적.
3. 결과 반환:
   • visited[K]: K에 도달한 최소 시간.
   • ways[K]: K에 도달하는 모든 경로의 수.

부가 질문

MAX = min(max(N, K) * 2, 100001) # 범위 제한 이게 더 효율적이지?

네, **MAX = min(max(N, K) * 2, 100001)**로 설정하는 방식은 MAX = 100001을 고정하는 것보다 더 메모리 효율적일 수 있습니다. 이유는 다음과 같습니다:

장점

1. 동적 범위 제한:
   • 수빈이(N)과 동생(K)의 위치가 멀리 떨어져 있지 않을 경우, MAX 값을 적절히 줄여서 메모리 사용량을 최소화할 수 있습니다.
   • 예를 들어, N=2, K=10이라면, MAX=min(10×2,100001)=20.이렇게 불필요한 공간을 탐색하지 않아 효율적입니다.
2. 안전한 동작:
   • 동적 범위를 설정하더라도 최대 범위를 100001로 제한하므로, 항상 문제에서 주어진 입력 제한 범위 내에서 동작합니다.
3. 시간 절약:
   • 불필요하게 넓은 범위를 탐색하지 않으므로 BFS 큐에 삽입하는 작업과 메모리 접근 비용이 줄어듭니다.

내 생각

1. 잘 이해가 안된다. 여러번 봐야겠다.
2. 종료 조건을 설정하지 않았는데 데이터가 return 된다. 범위 끝까지 탐색하는 것으로 보인다.
3. 때로는 방문시간, 경로 수를 각각 리스트로 관리하는게 더 빠르고 효율적일 수 있다.
4. chatGPT 풀이코드에 데이터 출력 (MAX = 34)

queue: deque([5])
visited: [-1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([4, 6, 10])
visited: [-1, -1, -1, -1, 1, 0, 1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([6, 10, 3, 8])
visited: [-1, -1, -1, 2, 1, 0, 1, -1, 2, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([10, 3, 8, 7, 12])
visited: [-1, -1, -1, 2, 1, 0, 1, 2, 2, -1, 1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([3, 8, 7, 12, 9, 11, 20])
visited: [-1, -1, -1, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, -1, -1, -1, -1, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([8, 7, 12, 9, 11, 20, 2])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, -1, -1, -1, -1, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([7, 12, 9, 11, 20, 2, 16])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, -1, -1, -1, 3, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([12, 9, 11, 20, 2, 16, 14])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, -1, 3, -1, 3, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([9, 11, 20, 2, 16, 14, 13, 24])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, -1, 3, -1, -1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([11, 20, 2, 16, 14, 13, 24, 18])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, -1, 3, -1, 3, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([20, 2, 16, 14, 13, 24, 18, 22])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, -1, 3, -1, 3, -1, 2, -1, 3, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([2, 16, 14, 13, 24, 18, 22, 19, 21])
visited: [-1, -1, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, -1, 3, -1, 3, 3, 2, 3, 3, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([16, 14, 13, 24, 18, 22, 19, 21, 1])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, -1, 3, -1, 3, 3, 2, 3, 3, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
queue: deque([14, 13, 24, 18, 22, 19, 21, 1, 15, 17, 32])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, -1, 3, -1, -1, -1, -1, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
queue: deque([13, 24, 18, 22, 19, 21, 1, 15, 17, 32, 28])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, -1, 3, -1, -1, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0]
queue: deque([24, 18, 22, 19, 21, 1, 15, 17, 32, 28, 26])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, -1, 3, -1, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([18, 22, 19, 21, 1, 15, 17, 32, 28, 26, 23, 25])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([22, 19, 21, 1, 15, 17, 32, 28, 26, 23, 25])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([19, 21, 1, 15, 17, 32, 28, 26, 23, 25])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([21, 1, 15, 17, 32, 28, 26, 23, 25])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([1, 15, 17, 32, 28, 26, 23, 25])
visited: [-1, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([15, 17, 32, 28, 26, 23, 25, 0])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, -1, -1, 4, -1]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0]
queue: deque([17, 32, 28, 26, 23, 25, 0, 30])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, 5, -1, 4, -1]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 2, 0, 1, 0]
queue: deque([32, 28, 26, 23, 25, 0, 30])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, 5, -1, 4, -1]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 2, 0, 1, 0]
queue: deque([28, 26, 23, 25, 0, 30, 31, 33])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, -1, 4, -1, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 0, 1, 0, 2, 1, 1, 1]
queue: deque([26, 23, 25, 0, 30, 31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1]
queue: deque([23, 25, 0, 30, 31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([25, 0, 30, 31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([0, 30, 31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([30, 31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([31, 33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([33, 27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([27, 29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([29])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]
queue: deque([])
visited: [5, 4, 3, 2, 1, 0, 1, 2, 2, 2, 1, 2, 2, 3, 3, 4, 3, 4, 3, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5]
ways: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1]