[파이썬/Python] 백준 1326번: 폴짝폴짝

숨·2024년 9월 9일

코테

알고리즘 문제 풀이

목록 보기

69/105

📌 문제 : 백준 1326번

📌 문제 탐색하기

N : 징검다리의 개수 $(1 ≤ N ≤ 10,000)$
nums : 징검다리에 적힌 N개 정수 $(1 ≤ nums ≤ 10,000)$
a, b : 출발 징검다리와 도착 징검다리

개구리가 a번째 징검다리에서 b번째 징검다리까지 가는데 점프하는 횟수의 최솟값을 구하는 문제이다.

문제 풀이

⭐️ 개구리의 점프 방식

점프하려는 징검다리에 쓰여있는 수의 배수만큼 이동 가능❗️

a에서 b로 갈 수 없다면 -1 출력

1번 징검다리부터 N번 징검다리까지 존재하고 a, b는 1 이상 N 이하의 자연수이다.

a 위치에서 b 위치까지 이동하는 최소 횟수를 BFS를 통해 탐색한다.
1. 현 위치가 b 위치라면 → 탐색을 멈추고 횟수 반환
2. 아니라면 → 현 위치의 숫자 배수만큼 이동하면서 방문처리하고 최소 이동 횟수 탐색

🚨 탐색할 때 a, b가 순서를 의미한다.
→ 인덱스로 해당 징검다리에 적힌 숫자에 접근할 때 -1을 해주어야 한다는 것을 주의해야 한다.

최종적으로 이동 횟수가 0일 땐 -1을 출력, 아닐 땐 이동 횟수를 출력하도록 한다.

가능한 시간복잡도

BFS로 탐색하면서 각 노드(징검다리) 방문→ $O(N)$

최종 시간복잡도
최악의 경우 $O(N) = O(10,000)$ 이 되는데 이는 2초 내에 연산 가능하다.

알고리즘 선택

BFS로 징검다리의 최소 이동 횟수 탐색

📌 코드 설계하기

BFS 구현
1-1. 큐 정의 후 방문 처리
1-2. 큐가 빌 때까지 탐색 반복
1-2-1. 도착하면 탐색 종료
1-2-2. 해당 위치의 숫자만큼 이동하면서 탐색해 최소 횟수 계산
필요한 입력 받기
방문 리스트 정의
BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

자꾸 정답에 -1만 출력되었다.
bfs에서 탐색하면서 이동 횟수 카운트를 해주어야 하는데 빼먹었다.

2회차

        # 적힌 숫자만큼 이동하면서 탐색
        for i in range(v + nums[v], N, nums[v]):
            # 방문 처리
            if not visited[i]:
                visited[i] = 1
                queue.append(i)

                count += 1

개구리는 배수만큼 한번에 움직일 수 있는데 몇배수만큼 이동했는지로 카운트해서 예제 1에 대한 출력이 자꾸 4가 나왔다.
큐에 시작점과 이동 횟수를 함께 저장해서 이동한 후에 이동 횟수를 증가시키도록 변경했다.

3회차

# bfs 구현
def bfs(start, end):
    # 큐 정의
    queue = deque([(start, 0)])
    # 방문 처리
    visited[start] = 1
    # 큐가 빌 때까지 반복
    while queue:
        v, count = queue.popleft()

        # 도착하면 종료
        if v == end:
            return count

        # 적힌 숫자만큼 이동하면서 탐색
        for i in range(v + nums[v], N, nums[v]):
            # 방문 처리
            if not visited[i]:
                visited[i] = 1
                queue.append((i, count + 1))

    # 도착하지 못한 경우
    return 0

bfs를 위와 같이 구현했는데 예제는 맞았지만 틀렸다.
a와 b의 대소관계가 정해져 있지 않은데 a에서 b로 가기 위해 왼쪽 방향으로 이동하는 경우도 고려해주어야 했던 것이다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 구현
def bfs(start, end):
    # 큐 정의
    queue = deque([(start, 0)])
    # 방문 처리
    visited[start] = 1
    # 큐가 빌 때까지 반복
    while queue:
        v, count = queue.popleft()

        # 도착하면 종료
        if v == end:
            return count

        # 적힌 숫자만큼 오른쪽 이동하면서 탐색
        for i in range(v + nums[v], N, nums[v]):
            # 방문 처리
            if not visited[i]:
                visited[i] = 1
                queue.append((i, count + 1))

        # 적힌 숫자만큼 왼쪽 이동하면서 탐색
        for i in range(v - nums[v], -1, -nums[v]):
            # 방문 처리
            if not visited[i]:
                visited[i] = 1
                queue.append((i, count + 1))
    # 도착하지 못한 경우
    return 0

# N 입력
N = int(input())

# 숫자 입력
nums = list(map(int, input().split()))

# 출발, 도착 입력
a, b = map(int, input().split())

# 방문 리스트 정의
visited = [0] * N

# bfs 수행 (리스트는 인덱스 0부터 시작하므로 1 빼주기)
result = bfs(a - 1, b - 1)

# 결과 출력
if result == 0:
    print(-1)
else:
    print(result)