[Python] 백준 1326: 폴짝폴짝

 solved.ac 기준 Silver2

 난이도에 비해 유난히 낮은 정답률을 보여 풀게 된 문제이다. 하지만 문제를 해석해보면 BFS 활용 시 크게 어려운 문제는 아닌 듯 보이지만, 아마도 문제의 모호한 면이 문제의 정답률을 낮춘게 아닐까 하는 생각이다.

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1

5
1 2 2 1 2
1 5

예제 출력 1

1

나도 문제를 처음에 읽고는 바로 다리 위에 적힌 숫자의 배수를 기준으로 다음 노드를 정한다. 까지만 생각했다. 하지만 문제를 풀며 중요한 의문점이 하나 들었는데, 문제에서는 점프의 방향을 제한하지 않았다. 그러므로 어차피 우측으로 점프만 가능하다면 좌측으로 점프하는 코드를 넣더라도 영향을 끼치지 않을 것이라 생각해 좌측 방향으로 점프를 하는 케이스까지 탐색하도록 코드를 구성했다.

 

정답 코드

from collections import deque

# 변수 입력
N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())

# bfs 활용하여 최단 횟수 탐색
q = deque()
visited = [False] * N

q.append(a)
visited[a-1] = True
qlen = 1

count = 0
result = -1

while q:
    for _ in range(qlen):
        index = q.popleft()
        num = bridge[index - 1]

        if index == b:
            result = count
            q = []
            break

        # 우측으로 점프
        for nextIndex in range(index + num, N+1, num):
            if not visited[nextIndex - 1]:
                q.append(nextIndex)
                visited[nextIndex - 1] = True

        # 좌측으로 점프
        for nextIndex in range(index - num, 0, -num):
            if not visited[nextIndex - 1]:
                q.append(nextIndex)
                visited[nextIndex - 1] = True

    qlen = len(q)

    count += 1


print(result)

 

 단순한 BFS로 구성하였고, 한번 루프마다 현재 탐색 횟수(레벨)를 카운트한다. 그리고 탐색 중 목적지에 도달하게 되면 현재 카운트를 결과 값에 넘겨주고 탐색을 중단하여 결과를 출력한다. 만약 탐색 중 목적지에 도달하지 못한다면 결과값은 처음 초기화 된 -1이 출력된다.

 

 혹시 좌측 이슈가 없을 것 같아서 좌측 코드를 빼고 검사해본 결과 틀렸다고 나온다. 빠른 판단도 중요하지만 정확하게 문제를 분석하는 습관을 들이자.