algorithm/baekjoon

[백준] 14248번 점프점프 (파이썬)

support_u 2023. 3. 15. 13:09

문제

 

14248번: 점프 점프

첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출

www.acmicpc.net

코드

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

def DFS(start):
    global cnt
    visited[start] = True
    cnt += 1

    for _ in range(2):
        if (0 <= start + stone[start] < n and not visited[start + stone[start]]):
            DFS(start + stone[start])
        elif 0 <= start - stone[start] < n and not visited[start - stone[start]]:
            DFS(start - stone[start])


n = int(input())
stone = list(map(int, input().split()))
start = int(input())

visited = [False] * n
cnt = 0
DFS(start-1)

print(cnt)

해설

start는 1부터 시작이니까 start - 1로 DFS에 들어갔다.

True할 때 마다 cnt += 1하고 칸수에서 넘어가지 않으면서 visited가 False라면 재귀한다.

여기서 왼쪽으로 갈 때 빼게되면서 음수가 되지 않으려나? 생각해서 abs를 줬는데 그러면 표밖을 넘어가는거라 틀리니 유의하자!