DFS

그래프 탐색 알고리즘: DFS/BFS탐색(Search): 많은 양의 데이터 중 원하는 데이터 찾는 과정대표적인 그래프 탐색 알고리즘: DFS/BFS코딩 테스트에서 매우 자주 등장하는 유형스택 자료구조먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입구와 출구가 동일한 형태로 스택을 시각화 가능삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()Pythonstack = []stack.append(5)stack.append(2)stack.append(3)stack.append(7)stack.pop()stack.append(1)stack.append(4)stack.pop()print(stack[::-1]) # 최상단 원소부터 출력 [1, 3,..

DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 DFS -> 스택 / BFS -> 큐 예시 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 스택에서 원소 꺼내 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 2번을 반복 => 모든 칸이 스택에 1번씩 들어감 -> 시간복잡도는 칸이 N개일 때 O(N) (0, 0)과 상하좌우로 이어진 모든 파란칸 확인 (0, 0)에 방문했다는 표시 + 해당 칸 -> 스택에 넣음 스택이 빌 때까지 스택의 top을 빼고 해당 좌표의 상하좌우를 살펴보면서 스택에 넣어주는 작업 ..