on
[이것이 코딩테스트다] 7일차
[이것이 코딩테스트다] 7일차
본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.
Chapter 5 DFS/BFS
* 학습 전 미리 알아야 할 자료구조와 함수
1. 스택, 큐
- 스택 (Stack)
스택이란 선입후출 (First In Last Out, FILO) 자료구조로 차곡차곡 쌓아 올린 형태의 자료구조이다
스택은 python의 list로 구현이 가능하다 ( push -> append() / pop -> pop() )
- 큐 ( Queue )
큐란 선입선출(First In First Out) 자료구조이며 '공정한' 자료구조로 비유된다 (은행 대기줄과 같음)
파이썬의 collections 라이브러리의 deque 를 사용할 수 있다 (push -> queue.append() / pop -> queue.popleft() )
2. 재귀함수
자기자신을 다시 호출하는 함수
재귀 함수를 작성할 때 무한 루프를 방지하기 위해 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다
https://dojang.io/mod/page/view.php?id=2352
DFS (Depth-First Search) / 깊이 우선 탐색
스택 자료구조를 활용하며 다음과 같은 실행 과정을 거친다
1. 탐색 시작 노드 (최상단 노드)를 스택에 삽입하고 방문처리
2. 최상단 노드에 인접한 노드 중 방문하지 않은 노드에 방문 -> 방문하지 않은 노드가 없다면 스택에서 상단 노드 꺼내기
3. 2번을 더이상 할 수 없을 때까지 반복
코드로 구현하기
## 각 노드와 연결되어 있는 인접노드 리스트 생성 # 맨 첫번째 칸을 비운 이유 -> 노드 번호와 인덱스 일치시키기 위해 graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]] def dfs(graph, v, visited): ## 1부터 실행 visited[v] = True ## 방문한 곳 print (v, end = ' ') for i in graph[v]: ## 연결된 노드 중 가장 앞부터 탐색 if visited[i] == False: ## 이전에 안들린 곳 dfs(graph, i, visited) ## 재귀함수 ## 방문정보 리스트 visited = [False] * len(graph) dfs(graph, 1, visited) ## result # 1 2 7 6 8 3 4 5
BFS (Breadth-First Search) / 너비 우선 탐색
큐 자료구조를 활용하며 다음과 같은 실행 과정을 거친다
1. 탐색 시작 노드 (최상단 노드) 를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내고 해당 노드의 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문 처리
3. 2번을 더이상 할 수 없을 때까지 반복
해당 시점에서 인접한 모드를 한번에 큐에 넣는다는 특징
- 특정 조건에서의 최단경로 문제를 해결하기 위한 풀이로 많이 사용 됨 (각 간선의 cost가 모두 같을 때)
코드로 구현하기
from collections import deque graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]] def bfs (graph, start, visited): ## deque 큐 선언 queue = deque([start]) visited[start] = True ## 큐가 빌때까지 while queue: v = queue.popleft() print (v, end = ' ') for i in graph[v]: if visited[i] == False: queue.append(i) visited[i] = True visited = [False] * len(graph) bfs(graph, 1, visited) ## result # 1 2 3 8 7 4 5 6
from http://gammistory.tistory.com/17 by ccl(A) rewrite - 2021-12-07 00:26:23