📖그래프
▪ 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 함.
▪ 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것.
▪ 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현함.
📌프로그래밍에서 그래프를 표현하는 두가지 방식
인접 행렬
▪ 2차원 배열로 그래프의 연결 관계를 표현하는 방식.
▪ 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨.
인접 리스트
▪ 리스트로 그래프의 연결 관계를 표현하는 방식.
▪ 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함.
▪ 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보가 느림.(연결된 데이터를 하나씩 확인해야 하기 때문.)
▪ 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 행렬 방식에 비해 메모리 공간의 낭비가 적음.
-> 파이썬으로 인접 리스트를 이용해 그래프를 표현하고자 할 때에는 단순히 2차원 리스트를 이용하면 됨.
📖깊이 우선 탐색(DFS)
▪ 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
▪ 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘.
▪ 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요됨.
▪ 스택을 이용하는 알고리즘이기 때문에 재귀 함수를 이용했을 때 간결하게 구현 가능.
📌스택 자료구조를 이용한 DFS의 구체적인 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
📖너비 우선 탐색(BFS)
▪ 가까운 노드부터 탐색하는 알고리즘.
▪ 선입선출 방식인 큐 자료구조를 이용하는 것이 정석임.
▪ 구현할 때 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요됨.
▪ 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편임.
📌BFS의 구체적인 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 하낟.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
동작원리: DFS(스택), BFS(큐)
구현방법: DFS(재귀 함수 이용), BFS(큐 자료구조 이용)
📒이것이 취업을 위한 코딩테스트다 with 파이썬 책을 참고하여 작성하였습니다.
https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661
