dfs1 탐색 알고리즘 DFS/BFS 들어가기 전에 그래프를 통한 비교 그래프는 노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점(vertex)이라고도 한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현 할 수 있다. 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 일반적으로는 인접 리스트의 방식이 더 효율적이다. 인접 행렬의 경우, 정점의 개수 N만큼 도는 2중 for문을 돌려 두 정점 간에 간선이 존재하는지를 확인해야하기 때문이다. 인접 행렬의 시간 복잡도 : O(N²) DFS(깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색한다. 이름에서 알 수 있듯이 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 확인(탐색)하면 된다.. 2021. 4. 12. 이전 1 다음
