라떼는말이야

[solved.ac 실버2] 1326_폴짝폴짝 (파이썬, BFS, DP) 본문

알고리즘/코딩 테스트

[solved.ac 실버2] 1326_폴짝폴짝 (파이썬, BFS, DP)

MangBaam 2022. 7. 4. 16:59
반응형

https://github.com/mangbaam/CodingTest

 

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다. Contribute to mangbaam/CodingTest development by creating an account on GitHub.

github.com

밑의 사진을 클릭하면 문제 링크로 이동합니다

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

예제

힌트

1번 징검다리에 1이 쓰여 있으므로, 1의 배수인 4만큼을 한 번에 뛰어 5번 징검다리로 갈 수 있다.


나의 풀이

이 문제를 DP로도 분류해야 할 지는 잘 모르겠지만 BFS 기반에 DP가 접목된 방식으로 문제를 풀었다.

예제에서는 시작 지점보다 끝 지점이 더 오른 쪽에 있는 것만 보여줬지만 끝 지점이 더 오른쪽에 있다는 조건이 없었기 때문에 양쪽으로 탐색을 해야한다.

현재 위치를 i라고 했을 때 i 위치부터 다리 끝까지 i위치의 값 만큼 폴짝폴짝 뛰며 현재 위치까지의 이동 횟수 + 1을 저장한다.

예를 들어 현재 2번에 있고, 2번에 적힌 값이 3이고, 2까지 오는데 1만큼 이동했다면 5, 8, 11, ... 끝까지 탐색하면서 해당 위치에 2 (1 + 1)를 저장한다.

물론 반대 방향으로도 탐색한다.

그러다가 end를 만나면 해당 위치에 저장된 값을 반환하고 탐색을 끝낸다.

만약 끝까지 찾지 못했다면 -1을 반환한다.

from collections import deque

n = int(input())
bridge = [0] + list(map(int, input().split()))
start, end = map(int, input().split())


def bfs(s, e):
    q = deque([s])
    visited = [-1] * (n + 1)
    visited[s] = 0
    while q:
        now = q.popleft()
        for i in range(now, n + 1, bridge[now]): # 오른쪽 방향
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == e:
                    return visited[i]
        for i in range(now, 0, -bridge[now]): # 왼쪽 방향
            if visited[i] == -1:
                q.append(i)
                visited[i] = visited[now] + 1
                if i == e:
                    return visited[i]
    return -1 # 찾지 못한 경우


print(bfs(start, end))

채점 결

 

반응형
Comments