반응형
츄르사려고 코딩하는 코집사입니다.
1. [백준 알고리즘] 백준 14248번 점프 점프 파이썬(Python)
1) 문제번호 : 14248번
2) 문제 출처
https://www.acmicpc.net/problem/14248
2. 문제
영우는 개구리다 개굴개굴개굴
영우는 지금 n개의 돌이 일렬로 놓여있는 돌다리에 있다. 그리고 돌다리의 돌에는 숫자가 하나씩 적혀있다. 영우는 이 숫자가 적혀있는 만큼 왼쪽이나 오른쪽으로 점프할 수 있는데, 이때 돌다리 밖으로 나갈 수는 없다.
영우는 이 돌다리에서 자기가 방문 가능한 돌들의 개수를 알고 싶어한다. 방문 가능하다는 것은 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다는 뜻이다.
현재 위치가 주어졌을 때, 영우가 방문 가능한 돌들의 개수를 출력하시오.
3. 제약사항
4. 입력
첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000)
다음 줄에는 출발점 s가 주어진다.(1≤s≤n)
5. 출력
영우가 방문 가능한 돌들의 개수를 출력하시오.
6. 풀이
-
7. 소스 코드
import sys
input=sys.stdin.readline
n = int(input()) # 돌다리의 돌 개수
li = list(map(int, input().split())) # 돌다리
visit = [0 for _ in range(n)] # 방문
s = int(input())-1 # 시작점
queue = []
def BFS(start) :
global result
queue.append(start)
visit[start] = 1
result += 1
while queue :
node = queue[0]
del queue[0]
for i in [-li[node], li[node]] :
jump = node + i
if 0<=jump<n and visit[jump] == 0 :
queue.append(jump)
result += 1
visit[jump] = 1
result = 0 # 방문한 돌맹이 갯수
BFS(s)
print(result)
반응형
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
[백준 알고리즘] 백준 20125번 쿠키의 신체 측정 파이썬(Python) (0) | 2021.06.17 |
---|---|
[백준 알고리즘] 백준 20124번 모르고리즘 회장님 추천 받습니다 파이썬(Python) (0) | 2021.06.16 |
[백준 알고리즘] 백준 1629번 곱셈 파이썬(Python) (0) | 2021.06.15 |
[백준 알고리즘] 백준 16922번 로마 숫자 만들기 파이썬(Python) (0) | 2021.06.15 |
[백준 알고리즘] 백준 11725번 트리의 부모 찾기 파이썬(Python) (0) | 2021.06.12 |
[백준 알고리즘] 백준 3184번 양 파이썬(Python) (0) | 2021.06.12 |
[백준 알고리즘] 백준 15720번 카우버거 파이썬(Python) (0) | 2021.06.11 |
[백준 알고리즘] 백준 6996번 애너그램 파이썬(Python) (0) | 2021.06.11 |
최근댓글