그래프의 모든 노드를 탐색하는 방법으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다.
그래프의 노드를 탐색하기 위해서는 노드간 간선에 의해 연결된 인접한 노드 정보가 필요하며 이 정보들을 행렬(2차원 리스트) 또는 리스트 형태로 저장하여 사용한다.
🎈 인접 행렬은 불필요한 정보까지 저장하게 되어 메모리를 낭비하게 되지만 원하는 관계정보를 빠르게 조회할 수 있다.
🎈 인접 리스트는 메모리의 낭비는 없지만 원하는 관계 정ㅈ보를 조회하기 위해 선형으로 조회해야 하기 때문에 속도가 비교적 떨어질 수도 있다.
그렇기에 인접 행렬의 경우 문제에서 그래프 전체를 주어지고 구분해야할 경우에 무조건 인접행렬을 통해 풀어야 할 것이다.
반면에 인접리스트는 그래프 전체가 주어지지 않고 현재 노드로부터 인접 노드들만 주어지는 것을 확인할 수 있다면 인접리스트로 풀면 된다.