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

📍 문제 탐색하기

개구리가 일렬로 놓인 징검다리 사이를 배수 단위로 점프하면서 시작 지점 a에서 목표 지점 b까지 도달하는 최소 점프 횟수를 구하는 문제다.

특정 징검다리에 쓰인 숫자를 k라고 하면, k는 그 위치에서 점프할 수 있는 단위를 의미하며, 배수(±k,2k,3k,...)의 형태로만 이동이 가능하다.

• 입력 범위:
  • 징검다리 개수 N: 최대 10,000
  • 각 징검다리에 쓰인 숫자 k: 최대 10,000
  • a,b: 시작점과 도착점으로 1 ≤ a,b ≤ N

---

가능한 시간복잡도

문제를 해결하기 위해 a에서 b까지 탐색해야 한다.

 

O(N): 

N=10,000: 즉 최대 10,000번의 방문과 연산이 일어난다. 따라서 1억 연산 이하로 충분히 제한 시간 안에 처리가 가능하다.
BFS를 이용하여 배수 형태로 이동 가능한 경로만을 탐색하면 효율적으로 해결할 수 있다.

---

알고리즘 선택

O(N)으로 처리가 가능하고, 최소 몇 번 점프했는지를 구해야하는 문제이므로,

탐색 알고리즘 중에서 최단 경로를 찾는 데 적합한 너비 우선 탐색(BFS)를 선택했다.
BFS를 통해 문제에서 요구하는 최소 점프 횟수를 효율적으로 구할 수 있다.

---

📍 코드 설계하기

1. 문제의 Input을 받는다.
2. 징검다리 개수 N과 각 징검다리에 적힌 숫자 배열을 정의한다.
3. BFS를 통해 시작점 a에서 목표 지점 b까지 탐색한다.
   • 현재 위치에서 배수 단위로 이동 가능한 지점만 탐색하며 큐에 추가한다.
   • 방향은 양방향(왼쪽, 오른쪽)을 모두 고려해야 한다. -> 이거 고려 안해서 틀렸다. ㅠㅠ

---

📍 시도 회차 수정 사항

1차 시도 (틀림) ❌

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

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())

visited = [False] * (N+1) 

def bfs(start): # start: 위치
    visited[start] = True
    queue = deque([(start, 0)]) # 현재위치, 점프 횟수
    
    while queue:
        current, jump = queue.popleft()
        
        if current == b:
            return jump
        
        num = bridge[current - 1] # 징검다리에 적힌 숫자
        
        mul = 1
        while True:
            next_pos = current + num * mul
            if next_pos > N:
                break
            if not visited[next_pos]:
                queue.append((next_pos, jump + 1))
                visited[next_pos] = True
            mul += 1
            
    return -1


result = bfs(a)
print(result)

오른쪽으로만 점프하도록 구현했다. 왼쪽 방향 탐색이 없어 틀렸다. 양방향 탐색을 구현해주어야 한다.

2차 시도 (맞음) ✅

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

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())

visited = [False] * (N+1) 

def bfs(start): # start: 위치
    visited[start] = True
    queue = deque([(start, 0)]) # 현재위치, 점프 횟수
    
    while queue:
        current, jump = queue.popleft()
        
        if current == b:
            return jump
        
        num = bridge[current - 1] # 징검다리에 적힌 숫자
        
        mul = 1
        while True:
            next_pos = current + num * mul
            if next_pos > N:
                break
            if not visited[next_pos]:
                queue.append((next_pos, jump + 1))
                visited[next_pos] = True
            mul += 1
            
        mul = 1
        while True:
            next_pos = current - num * mul  
            if next_pos < 1:  
                break
            if not visited[next_pos]:
                visited[next_pos] = True
                queue.append((next_pos, jump + 1))
            mul += 1
            
    return -1


result = bfs(a)
print(result)

양방향 탐색을 구현했으나,

왼쪽, 오른쪽 점프 코드를 각각 작성하여 점프 방향별 코드가 중복되는 느낌이 들었다.

중복을 없애고 싶었다!

최종 코드 (맞음) ✅

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

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())

visited = [False] * (N+1) 

def bfs(start): # start: 위치
    visited[start] = True
    queue = deque([(start, 0)]) # 현재위치, 점프 횟수
    
    while queue:
        current, jump = queue.popleft()
        
        if current == b:
            return jump
        
        num = bridge[current - 1] # 징검다리에 적힌 숫자
        
        for direction in [1, -1]:
            mul = 1
            while True:
                next_pos = current + num * mul * direction
                if next_pos < 1 or next_pos > N:  
                    break
                if not visited[next_pos]:
                    visited[next_pos] = True
                    queue.append((next_pos, jump + 1))
                mul += 1
            
    return -1


result = bfs(a)
print(result)

점프 방향(왼쪽, 오른쪽)을 변수화하여 중복 코드를 제거하였고, BFS를 통해 최소 점프 횟수를 정확히 계산할 수 있도록 최적화했다!