[알고리즘] 백준 14248 파이썬 - 점프 점프

 

14248번: 점프 점프

문제

영우는 개구리다 개굴개굴개굴

영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.

영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.

현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.

 

문제풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) 
n=int(input())
arr=list(map(int,input().split()))
x=int(input())
cnt=1
visited=[0]*(n+1)
def dfs(x):
	#01
    global cnt
    visited[x]=1
    #02
    for i in (x+arr[x], x-arr[x]):
        if 0<=i<n and visited[i]==0:
            cnt+=1
            visited[i]=1
            dfs(i)
#03
dfs(x-1)
print(cnt)

- #01 : 방문 가능한 돌을 세기위해 cnt를 global 해준다.

- #02 : x의 위치에서 움직일 수 있는 2개의 값을 i에 넣고,

           i가 0<=i<n이고 방문하지 않았다면, cnt에 1을 더하고 visited도 1로 바꿔준다.

- #03 : 최종적으로 dfs를 모두 돌았을 때 생긴 cnt를 출력한다.