99클럽 코테 스터디 31일차 TIL + DFS

[오늘의 학습 키워드 및 문제]
- 백준의 "점프 점프" 문제를 풀었다.
- 오늘은 DFS/BFS가 주제다.
- 문제를 읽고 나서 DFS가 편하겠다고 생각했다.

[나의 코드]

n = int(input())
nums = list(map(int, input().split()))
s = int(input())

visited = [False] * n
answer = 1

def dfs(start):
    global answer
    
    for i in (start + nums[start], start - nums[start]):
        if 0 <= i < n and not visited[i]:
            answer += 1
            visited[i] = True
            dfs(i)

dfs(s - 1)
print(answer)

문제에 방문 가능한 모든 돌의 개수를 적는 것이므로 visited 배열이 필요하다는 것을 알 수 있다. 그래서 만들었다.
그리고 시작하는 것부터 셀 것이기 때문에 answer는 1부터 시작했다.

문제를 읽어보면 '앗! 이것은 DFS가 더 편하겠구나'를 아는데, 설명은 못하는 영역이다.
어차피 해당 숫자가 적혀 있는 만큼 왼쪽 또는 오른쪽으로 이동하는 거니까 두 가지의 경우의 수를 for문에 돌려준다.

그리고 돌다리 밖으로 나갈 수 없으므로 가능한 영역을 설정하고, 방문하지 않았다면 다음 노드를 깊이 우선 방법으로 탐색한다. 그리고 답을 출력하면 된다.

[오늘의 회고]
- 오늘 문제는 백준의 다른 문제와 비슷했다. 그것도 다시 풀어보면 좋을 것 같다.
- 요즘 너무 졸렵다. 맨날 조는 듯하다. 여름잠 자러 동굴로 들어가야겠다. 끝!