[백준][Python] 14248 점프 점프

그래프, dfs / 실버 2

🪨

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

14248번: 점프 점프

 

내 풀이

def dfs(s):
    if s > 0 and s <= n and not visited[s]:
        visited[s] = True
        dfs(s-stones[s-1])
        dfs(s+stones[s-1])

n = int(input())
stones = list(map(int, input().split()))
s = int(input())
visited = [False] * (n+1)

dfs(s)

print(visited.count(True))

 

dfs(깊이 우선 탐색)으로 풀었다.

 

 

코드 설명

 

dfs의 매개변수로 현재위치(s)가 주어진다.현재 위치(s)가 범위를 벗어나지 않았고(돌다리 밖으로 나가지 않았고), 방문하지 않았던 돌다리였다면

if s > 0 and s <= n and not visited[s]:

 

방문 처리를 해준다. (방문 가능한 돌임을 알림)

visited[s] = True

 

그리고 돌에 적혀있는 숫자만큼 왼쪽으로 이동하는 경우와 오른쪽으로 이동하는 경우를 처리한다.

이동하게 될 위치를 매개변수로 넘겨 dfs를 호출한다.

dfs(s-stones[s-1]) # 왼쪽으로 이동
dfs(s+stones[s-1]) # 오른쪽으로 이동

이때 stones의 인덱스에 주의한다. s-1 !!

 

방문 가능한 돌의 개수가 정답이다.

visited.count(True)