[백준] 14248 : 점프점프 (Python)

 

출처 : https://www.acmicpc.net/problem/14248

 

---

 

아이디어

해당 문제는 그래프 탐색 유형으로 분류할 수 있으며, '점프를 해나가는 과정'의 의미를 파악하면 쉽게 해결할 수 있다. 예제를 통해, 그 의미를 살펴보자.

예제 입력 1번 케이스를 기준으로, 3번돌의 다음 방문 돌을 오른쪽으로 간다고 가정해보자. 이 때, 돌의 방문 순서는 다음과 같다.

3번돌 -> 5번돌 -> 4번돌 -> 2번돌 -> 방문불가(범위초과)

이는 함수로써 다음과 같이도 쓸 수 있다.

f(3) -> f(f(3)) -> f(f(f(3))) -> f(f(f(f(3)))) -> 방문 불가

즉, '점프를 해나가는 과정'은 '재귀 함수'와 동일하다. 이를 토대로, 우리는 그래프로 다음과 같이 시각화할 수 있다.

예제 입력 1번 케이스, 그래프 시각화

그래프 정의는 다음과 같다.

• 노드 : 돌 번호
• 간선 : 왼쪽 점프, 오른쪽 점프

시각화 사진을 통해 알 수 있듯이, 특정 돌을 중복으로 탐색할 수도 있다. 이런 경우는 비효율적이므로, 방문처리배열을 통해 탐색을 진행해야한다.

이 방문처리 배열에는 각 노드의 방문 정보(0 또는 1)이 담겨져있으므로, 이 배열을 통해 정답 처리를 해줄 수 있다.

---

정리하자면, 점프를 해나가는 과정은 재귀와 동일하기 때문에 그래프로 나타낼 수 있다는 것이 이 문제의 핵심 인사이트이다. 또한, 요구사항은 방문 여부만 제시하기에, BFS와 DFS 모두 사용 가능하다.

필자는 DFS로 구현하였고, n은 10만까지 입력되기 때문에 탐색 깊이가 10만까지 이루어져야 한다는 것을 주의하자.

 

정답 코드

# https://www.acmicpc.net/problem/14248
# 점프 점프
# 그래프 탐색

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(x):
    left_child=x-A[x]
    right_child=x+A[x]
    # A[i]만큼 왼쪽 돌로 갈 수 있고, 처음 방문하면
    if 0<=left_child<n and not visited[left_child]:
        visited[left_child]=1
        dfs(left_child) # 왼쪽 돌로 이동해서 다음 점프 탐색
    # A[i]만큼 오른쪽 돌로 갈 수 있고, 처음 방문하면
    if 0<=right_child<n and not visited[right_child]:
        visited[right_child]=1
        dfs(right_child) # 오른쪽 돌로 이동해서 다음 점프 탐색

n=int(input())
A=[*map(int,input().split())]
root=int(input()) # 시작돌(A배열의 인덱스)
root-=1

visited=[0]*n # 방문배열
visited[root]=1
dfs(root)
print(sum(visited))