[백준] 폴짝폴짝 (1326번)

난이도 : Silver2
Link : https://www.acmicpc.net/problem/1326
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색
풀이일자 : 2024년 9월 9일

📌 문제 탐색하기

개구리는 a번째 징검다리에서 b번째 징검다리까지 최소 몇번 점프를 해야하는지 구하는 문제이다.

조건)
개구리는 징검다리에 쓰여있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

가능한 시간복잡도

징검다리의 개수는 N(1<= N <= 10,000)이므로 최악인 시간복잡도인 항상 한칸만 점프할 때를 가정해도 10,000번만 반복하면 되기 때문에 문제 없어 보인다.

📌 문제 접근 방법

개구리의 위치의 숫자를 파악하고 숫자의 배수중 징검다리로 부터 가장 멀리 떨어진 곳으로 도달하는 것이 가장 중요하다.

BFS를 이용하여 방문횟수를 파악하여 B번째 징검다리에 도달했을 때 점프 횟수를 반환하면 될것이라고 판단한다.

문제에서 오른쪽으로만 점프하는지, 왼쪽으로 점프하는지 명시되어 있지 않기 때문에 둘다의 경우를 확인해야 한다.

📌 코드 설계하기

1. N을 입력받는다.
2. bridge와 a,b를 입력받는다. bridge는 인덱스의 헷갈림을 줄이기 위해 0번째 인덱스를 추가한다.
3. BFS 함수를 작성한다.
   - queue에 시작 위치를 설정한다.
   - visted 리스트를 -1로 초기화 시킨다.
   - visited[start] 를 0으로 초기화 시켜 첫번째 위치를 방문했다는 것을 인지 시킨다.
   - queue에 원소가 존재할 경우 while문을 반복한다.
   - 오른쪽으로 이동할 경우, 왼쪽으로 이동할 경우로 나눠 for문을 작성한다

   1. bridge[now]만큼 간격을 주어 점프 할 수 있는 곳을 확인한다.
   2. if visited[i] == -1 이라면 방문한적이 없는 징검다리이므로 , 해당 징검다리를 몇번 점프해야 방문 할 수 있는지 visited[i] 에 추가한다.
   3. 만일 i 가 끝에 가고 싶은 징검다리라면 해당 점프 횟수를 반환한다.
   4. 전체를 탐색해도 가고싶은 징검다리가 나오지 않는다면 -1을 반환한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (왼쪽으로부터 오른쪽으로만 징검다리를 이동 가능한 줄 알았다.)
   (왼쪽방향과 오른쪽 방향을 확인하기 위해 BFS를 활용하여 문제를 해결하였다.)

from collections import deque

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

def BFS(start, end):
    queue = deque([start]) #시작 위치 설정
    visited = [-1] * (N+1) # 방문 노드 표시 (방문하지 않은곳 -1)
    visited[start] = 0 #방문시 0
    while queue:
        now = queue.popleft() #현재 노드 탐색
        # 오른쪽 방향 탐색
        for i in range(now, N + 1 , bridge[now]):
            if visited[i] == -1 :
                queue.append(i)
                visited[i] = visited[now] + 1 #i까지 도달하는데 필요한 점프 횟수 추가
                if i == end:
                    return visited[i]
        # 왼쪽 방향 탐색
        for i in range(now, 0, -bridge[now]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[now]
                if i == end:
                    return visited[i]
    return -1

print(BFS(a, b))

📌 정답 코드

from collections import deque

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

def BFS(start, end):
    queue = deque([start]) #시작 위치 설정
    visited = [-1] * (N+1) # 방문 노드 표시 (방문하지 않은곳 -1)
    visited[start] = 0
    while queue:
        now = queue.popleft() #현재 노드 탐색
        # 오른쪽 방향 탐색
        for i in range(now, N + 1 , bridge[now]):
            if visited[i] == -1 :
                queue.append(i)
                visited[i] = visited[now] + 1 #i까지 도달하는데 필요한 점프 횟수 추가
                if i == end:
                    return visited[i]
        # 왼쪽 방향 탐색
        for i in range(now, 0, -bridge[now]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[now] + 1
                if i == end:
                    return visited[i]
    return -1

print(BFS(a, b))