백준[ 14248 | Python ] 점프 점프

문제

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

풀이

1차원 배열에서의 DFS탐색을 하는 문제다.
같은 크기의 방문체크 배열을 만들어주고 이에 따라 탐색한다.
이 때 탐색하는 돌에 쓰여있는 숫자는 앞으로도, 뒤로도 갈 수 있기 때문에 이 점을 유념 해두어야 한다.

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

n = int(input().rstrip())
v = [0]*(n+1)
bridge = list(map(int, input().split()))
s = int(input().rstrip())
cnt = 1
def dfs(x):
    global cnt
    for i in range(2):
        if not i:
            nx = x+bridge[x]
        else:
            nx = x-bridge[x]
        if 0<=nx<n and not v[nx]:
            v[nx] = 1
            cnt += 1
            dfs(nx)
dfs(s-1)
print(cnt)

생각 & 정리

차원이 작은 배열이라서 해결하기 어렵지 않았다.
하지만 앞, 뒤로 움직일 수 있다는 조건은 간과하기 쉬웠기 때문에 예제를 먼저 분석하는 것이 중요하다는 것을 새삼느끼게 되었다.