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

오늘의 문제 - DFS/BFS

백준 14248번 점프 점프

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

---

풀이 및 접근 방식

DFS 풀이

from collections import deque
import sys

n = int(sys.stdin.readline())	# 돌의 개수
rocks = list(map(int, sys.stdin.readline().split()))	# 각 돌에 적혀있는 숫자 리스트
s = int(sys.stdin.readline())	# 시작 위치

visited = [False for _ in range(n)]	# 돌 방문 체크

def dfs(x):
    visited[x] = True
    
    lx = x - rocks[x]	# 왼쪽 칸 이동
    rx = x + rocks[x]	# 오른쪽 칸 이동
	
    if 0 <= lx < n:
        dfs(lx)
    if 0 <= rx < n:
        dfs(rx)

dfs(s-1)
ans = 0
for v in visited:	# 방문한 돌 개수 세기
    if v:
        ans += 1

print(ans)

풀이

1. 입력 받기 및 방문 리스트 생성
2. DFS 정의
   
   • dfs(x) 함수는 현재 위치 x에서 출발하여 방문할 수 있는 모든 돌을 탐색.
   • 현재 위치를 방문했다고 표시한 후, 왼쪽(x - rocks[x])과 오른쪽(x + rocks[x])으로 이동.
   • 이동한 위치가 유효한 인덱스 내에 있을 경우 재귀적으로 dfs 함수를 호출하여 이동한 위치에서 다시 탐색.
3. DFS 호출
   • s는 1부터 n까지의 범위를 가지므로, 인덱스로 넘겨주기 위해 s-1로 조정하여 dfs를 호출한다.
4. 결과 계산
   • visited 리스트에서 True인 값 세어 몇 개의 돌을 방문했는지 계산하여 출력.

BFS 풀이

from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start] = True
    count = 0
    
    while queue:
        x = queue.popleft()
        count += 1
        
        left_index = x - rocks[x]
        right_index = x + rocks[x]
        
        if 0 <= left_index < n and not visited[left_index]:
            visited[left_index] = True
            queue.append(left_index)
        
        if 0 <= right_index < n and not visited[right_index]:
            visited[right_index] = True
            queue.append(right_index)
    
    return count

# 입력 처리
n = int(input())
rocks = list(map(int, input().split()))
s = int(input())

visited = [False] * n

# BFS 호출 및 결과 출력
result = bfs(s-1)
print(result)

---

회고

DFS와 BFS를 한번 더 정리하고 넘어갈 수 있는 문제였다.
그래프 맵 뿐만 아니라 이런 선형 리스트 탐색같은 경우에도 DFS와 BFS를 사용할 수 있는 것을 알아두면 좋을 것 같다.