백준 1326번: 폴짝폴짝 [Python]

작성일 | In
실버 II 실버 II

문제

폴짝 폴짝
간단한 BFS 문제입니다.

풀이

먼저 그래프를 만들어줍시다. 여기서는 인접 리스트로 만들어 보겠습니다.

개구리는 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있습니다. 판별을 편하기 위해 인덱스를 1부터 사용했습니다.

1
2
3
4
5
6
7
8
9
10
11
# 입력
n = int(input())
stones = [None] + list(map(int, input().split()))
departure, arrival = map(int, input().split())

# 인접 리스트 구현
adj = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i != j and abs(j - i) % stones[i] == 0: # 배수만큼 떨어져 있다면
            adj[i].append(j)

그리고 구현한 그래프를 BFS로 탐색하면서 도착지까지 최소 횟수를 구해줍시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
count = [None for _ in range(n + 1)] # count[i] : i번째 징검다리까지 가는 데 걸리는 최소 횟수
count[departure] = 0
queue = deque([departure])
while queue:
    now = queue.popleft()
    if now == arrival:
        break

    for next_ in adj[now]:
        if count[next_] is not None:
            continue
        count[next_] = count[now] + 1
        queue.append(next_)

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque

n = int(input())
stones = [None] + list(map(int, input().split()))
departure, arrival = map(int, input().split())

adj = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i != j and abs(j - i) % stones[i] == 0:
            adj[i].append(j)

count = [None for _ in range(n + 1)]
count[departure] = 0
queue = deque([departure])
while queue:
    now = queue.popleft()
    if now == arrival:
        break

    for next_ in adj[now]:
        if count[next_] is not None:
            continue
        count[next_] = count[now] + 1
        queue.append(next_)

print(count[arrival] if count[arrival] is not None else -1)

백준 1326번: 폴짝폴짝 [Python]