하루일문
[백준] 14248번 점프점프 (파이썬) 본문
문제
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를 줬는데 그러면 표밖을 넘어가는거라 틀리니 유의하자!
'algorithm > baekjoon' 카테고리의 다른 글
[백준] 1076번 저항(파이썬) (0) | 2023.03.17 |
---|---|
[백준] 1032번 명령 프롬프트 (파이썬) (0) | 2023.03.16 |
[백준] 1021번 회전하는 큐(파이썬) (1) | 2023.03.14 |
[백준] 1009번 분산처리(파이썬) (1) | 2023.03.13 |
[백준] 11060번 점프점프(파이썬) (0) | 2023.03.12 |