
[Algorithm] DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) : 파이썬 예제 코드 + 인접 행렬, 인접 리스트
·
Computer Science/Algorithm
DFS, BFS를 설명하기 전에, 그래프 표현의 2가지 방식은 인접 행렬과 인접 리스트에 대해 알아봅니다! 인접 행렬 (Adjacency Matrix) - 2차원 배열에 각 노드가 연결된 형태를 기록 - 연결되지 않은 노드의 비용은 무한으로 작성한다 INF = int(1e9) graph = [ [0, 1, 1, 1], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ] 인접 리스트 (Adjacency List) - 모든 노드에 대해 연결된 노드에 대한 정보를 연결하여 저장 adj = [[] for _ in range(4)] adj[1].append(2) adj[1].append(3) adj[1].append(4) adj[3].append(3) adj[4].append(3) - 가..