99클럽 코테 스터디 6일차 TIL + DFS 알고리즘

❇️오늘의 학습 키워드 : DFS 알고리즘

 

DFS 알고리즘?

- 그래프 탐색 알고리즘으로, 노드와 노드를 잇는 간선을 따라가며 모든 노드를 방문하는 방식

- 트리나 그래프의 구조를 탐색하거나 경로를 찾는 데 사용며, 재귀나 스택을 활용하여 쉽게 구현할 수 있음!

- 미로 탈출, 연결 요소 찾기, 경로 찾기에 많이 활용

- but 최단 경로를 보장 x

DFS 알고리즘의 동작 원리

    (1) 현재 노드에서 갈 수 있는 한 최대로 깊게 탐색

    (2) 더 이상 갈 곳이 없으면 직전 노드로 되돌아가 다른 경로를 탐색

    (3) 모든 노드를 방문할 때까지 반복

DFS 알고리즘의 특징

- 후입선출 구조인 스택을 사용해 탐색

- 방문 여부를 visited 리스트로 기록

- 모든 노드를 한 번씩 방문 -> 시간 복잡도는 O(V + E)

DFS 알고리즘 코드 예제

(1) 재귀

def dfs_recursive(graph, node, visited):
    visited[node] = 1  # 현재 노드 방문 표시
    
    for neighbor in graph[node]:  # 인접 노드 탐색
        if visited[neighbor] == 0:  # 방문하지 않은 노드가 있다면
            dfs_recursive(graph, neighbor, visited)

(2) 스택

def dfs_stack(graph, start):
    visited = [-1] * (len(graph) + 1)
    stack = [start]
    
    while stack:
        node = stack.pop()  # 스택에서 노드 하나 꺼내기
        
        if not visited[node]:  # 방문하지 않은 노드인 경우
            visited[node] = 1
            
            # 인접 노드를 스택에 추가 (역순으로 추가해 왼쪽부터 방문)
            for neighbor in reversed(graph[node]):
                if not visited[neighbor]:
                    stack.append(neighbor)

 

❇️오늘의 회고

  - 오늘자 문제를 푸는데, 플로이드 워셜 알고리즘으로 풀면 시간초과가 나서 DFS를 이용하는 방법도 공부하였다!

  - DFS/BFS 알고리즘만큼은 빠삭하게 이해하고 내 것으로 만들어야 될 것 같다는 생각이 자꾸만 든다...🔥홧팅.

  - DFS/BFS 알고리즘을 어떨 때 어떻게 사용해야되는지는 문제를 많이 풀어보면서 감을 잡아봐야겠다!