Algorithm/Concept

[Algorithm/Python] BFS/DFS 이해하기

💡 DFS(Depth First Search) : 깊이 우선 탐색 → 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 미로에 갇혔을 때, 가던 길이 막히면 가장 최근에 있었던 갈림길로 되돌아간다 → 스택 연상 가능 ** 스택에 지나온 경로를 저장하자 ** 탐색 시작 노드를 스택에 push → 방문 처리 스택이 공백이 아니면 하나의 위치를 꺼냄 → 현재 위치 → 방문 처리 꺼낸 현재 위치가 출구 → 탐색 성공 출구가 아니다 → 상하좌우 이웃한 방들을 살펴봄 → 갈 수 있는 모든 방들을 스택에 push → 반복 O(N)의 시간이 소요되고, DFS는 스택을 사용하는 알고리즘 → 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. [구현] graph = [[], [2, 3, 8], [1, ..