[알고리즘/백준] 1326번 폴짝폴짝 Python 파이썬

 

이번 문제는 BFS를 통해서 풀어야 하는 문제로 난이도가 급상승한 것 같습니다.  

 

 

처음에는 이걸 일일이 어떻게 계산해주지 고민하느라 머리가 깨지는 줄 알았습니다. 그러다가 나중에야 DFS랑 BFS를 떠올렸습니다. 그 중에서 큐에 넣는게 편할 거 같아서 BFS를 썼습니다. 그렇게 코드를 짰지만 통과가 안되길래 2차 머리가 아팠는데 결국 인터넷을 힘을 빌려서 문제를 알아냈습니다..... 따로 징검다리 시작점이 따로 주어지기 때문에 앞으로도 "뒤로도" 갈 수 있다는 점입니다....허허허

 

다음과 같은 코드로 통과하였습니다.

 

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
N_list = [0] + list(map(int, input().split()))
a, b = map(int, input().split())

def bfs(start, end):
    q = deque([start])
    visited = [-1] * (N+1)
    visited[start] = 0
    while q:
        pos = q.popleft()
        for i in range(pos, N+1, N_list[pos]):
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[pos] +1
                if end == i:
                    return visited[i]
        for i in range(pos, 0, -N_list[pos]):
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[pos] + 1
                if end == i:
                    return visited[i]
    return -1

print(bfs(a, b))

 

하다가 모르면 인터넷 찾아서 풀이보는게 최고인 거 같습니다. 물론 충분히 고민할 시간을 가져야 실력이 늘긴하지만 그것도 10분이상 모르겠으면 그냥 찾아서 이해하는게 제일 효율적인 것 같습니다.