[백준1326] / 폴짝폴짝 - 그래프(BFS)

 

백준1326

 

 

푼 날짜 : 2024.08.18

푼 문제 : [1326] / 폴짝폴짝

사용한 언어 : python

 

 

푼 방법 :

너비 우선 탐색으로 접근하였다.

 

 

어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

 

 

 

 

이 부분이 중요한데 앞으로 가든 뒤로 가든 현재 위치의 징검다리의 수의 배수만큼만 이동한다는 거 !

예시를 들자면 현재위치가 인덱스 4번이고 4번 징검다리에 쓰여 있는 수가 3이라면, 

(내)이해를 돕기위한 그림

 

이렇게 1과 7로 이동할 수 있다.

만약 배열이 더 길다면 인덱스 7, 10, 13, 16 .... 이렇게 갈 수 있다! 

 

 

추가적인 테스트케이스를 첨부해보자면, 

 

테스트케이스

 

 

마지막 3번 테케는 질문게시판에 다른 분이 올려주신 부분을 손으로 그려봤다.

 

 

순서대로 

N - 징검다리 수
graph_ - N개의 징검다리와 징검다리 숫자
a, b - 시작인덱스, 도착인덱스

 

이다.

 

 

따라서 현재 위치 기준으로 왼쪽 방향과 오른쪽 방향을 다 고려해야하며,
반복문을 두 개로 나누어 구현해도 되지만 한 번에 정리해서 하나의 반복문으로 구현하고 싶었기에 아래처럼 작성했다.

 

현재 인덱스와 현재 인덱스에 써있는 숫자를 구하여

인덱스%숫자 부터 N+1까지 숫자 만큼 반복 하도록 했다.

for i in range(now%num, N+1, num):

 

 

예를 들어 아래처럼 징검다리의 길이가 11 이고 현재 위치가 3이면서 해당 징검다리 숫자가 4라면,

 

(내)이해를 돕기위한 그림

 

인덱스 = 3
숫자 = 4
N = 11

 

이므로

#for i in range(3%4, 11+1, 4): <- 제일 앞에 0을 임의로 추가하여 N까지 반복하기 위해 +1을 해주었다
for i in range(3, 12, 4):

 

이렇게 된다.

따라서 인덱스 3, 7, 11 이렇게 반복하게 된다!

 

이렇게 구현하면 왼쪽 방향과 오른쪽 방향을 나누어 구현하지 않아도 하나의 반복문으로 배수 구간 처리를 할 수 있다 :)

 

 

코드 :

import sys
from collections import deque

N = int(sys.stdin.readline())

graph_ = list(map(int, sys.stdin.readline().split()))
graph_.insert(0, 0) # index계산을 편하게 하기 위함

visited = [-1 for _ in range(10001)]
a, b = map(int, sys.stdin.readline().split())

def BFS(graph_, visited, v):
    queue = deque([v])
    visited[v] = 0

    while queue:
        now = queue.popleft()
        num = graph_[now]
        for i in range(now%num, N+1, num): # 징검다리에 쓰여 있는 수의 배수만큼만 반복
            nx = i
            if 0<nx<=N and visited[nx] == -1:
                queue.append(nx)
                visited[nx] = visited[now] + 1


BFS(graph_, visited, a)
print(visited[b])

 

 

처음에 문제를 제대로 이해하지 못해서 조금 자세하게 적어보았다.

나머지는 일반적인 BFS 구현 방식과 비슷하다!

 

 

역시 이해가 안될 땐 손으로 직접 그리는게 최고인 것 같다!