[Algorithm] DFS와 BFS 기본 개념 및 관련 문제들 (python)
2021.04.23
시작하기에 앞서.. 그래프의 표현 방법 그래프는 표현하는 방법을 크게 두가지로 나눌 수 있습니다. 하나는 인접 행렬, 다른 하나는 인접 리스트입니다. 1. 인접 행렬 (Adjacency Matrix) 2차원 배열로 그래프의 연결관계를 표현하는 방식입니다. INF = float('inf') graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] 2. 인접 리스트 (Adjacency List) 리스트로 그래프의 연결관계를 표현하는 방식입니다. 저의 경우에는 딕셔너리나 collections에 있는 defaultdict를 사용합니다. 둘이 똑같이 키-값의 구조라서 빠른 접근이 가능하다는 점에서 사용하기 편리한 것 같습니다ㅎㅎ 아래는 defaultdict를 사용한 방법입니다. gra..