[baekjoon] 백준 1326번(파이썬): 폴짝폴짝

문제

1326번: 폴짝폴짝

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 반복문을 통해 건너야 하는 다리를 모두 탐색한다.

- 2개의 반복문을 통해 현재 다리에서 앞으로 가는 경우와 뒤로 가는 경우를 나눠 탐색한다.

- 탐색 중 탐색하지 않은 다리가 나타나면 건너야 하는 다리 리스트에 추가하고 그 다리까지 점프한 수를 초기화한다.

- 그때 탐색한 다리가 b번 다리라면 그때 탐색한 다리까지 점프한 수를 출력한다.

- 모든 다리를 탐색한 후에도 b번 다리를 가지 못했다면 -1을 출력한다.

코드

import sys
from collections import deque


def bfs():
    queue = deque([a - 1]) # a번째 다리부터 탐색
    visited = [-1] * 100000
    visited[a - 1] = 0 # a 번째 다리는 시작점으로 0으러 초기화

    # 건너야 하는 다리를 모두 탐색
    while queue:
        target = queue.popleft() # 현재 건너는 다리

        # 반복문을 통해 현재 다리에서 앞으로 건넌다.
        for i in range(target, n, m[target]):
            # 탐색하지 않은 다리라면
            if visited[i] == -1:
                queue.append(i) # 건너야 하는 다리의 추가
                visited[i] = visited[target] + 1 # 점프 수 카운트

                # 현재 다리가 b번 다리라면 현재 다리까지 점프한 수를 출력
                if i == b - 1:
                    return visited[i]

        # 반복문을 통해 현재 다리에서 뒤로 간다.
        for i in range(target, -1, -m[target]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[target] + 1
                if i == b - 1:
                    return visited[i]

    # b번 다리를 가지 못했다면 -1 출력
    return -1


n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
a, b = map(int, sys.stdin.readline().split())
print(bfs())

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법