농's 개발 공부 이야기

그래프 순회/탐색 그래프의 각 정점을 방문하는 과정을 의미한다. 보통 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 두 가지로 분류하는데 DFS가 BFS보다 더 널리 쓰인다. DFS는 보통 스택 혹은 재귀로 구현하며 백트래킹에서 사용하기 좋고, BFS는 보통 큐로 구현하며 그래프 최단 경로를 구하는 문제에 용이하게 쓰인다. 그래프의 표현은 인접 행렬과 인접 리스트 두 가지 방법이 있다. 인접 리스트는 출발 노드를 키로, 도착 노드를 값으로 한 딕셔너리 형태로 표현할 수 있다. 이 때 도착 노드는 여러 개가 될 수 있으니까 리스트로 나타낸다. 인접 행렬은 이차원 배열로 나타내는데 출발 노드 행과 도착 노드 열에 간선이 존재하면 1, 없으면 0의 값을 넣게 된다. 인접 행렬은 노드의 개수가 간선의 개수..