언제나 휴일

[C언어 알고리즘] 6.2 깊이우선탐색(DFS) 알고리즘 지도에서 출발지와 목적지 사이의 경로 찾는 방법은 매우 다양합니다. 여기에서는 경로 탐색 알고리즘 중에서 동적 알고리즘 방식의 깊이우선탐색(DFS, Depth First Search) 알고리즘을 소개할게요. 깊이우선탐색 알고리즘은 출발지에서 다음 지점 중에 한 점으로 이동하고 해당 지점에서 다시 다음 지점으로 이동하는 것을 반복합니다. 만약 더 이상 이동할 곳이 없으면 이전 지점으로 다시 돌아와서 가지 않은 다른 지점으로 이동합니다. 이를 목적지에 도달할 때까지 반복하는 것입니다. 이와 같은 방법으로 문제를 해결하기 위해서는 이동하다가 막혔을 때 다시 돌아와서 다음 경로로 이동해야 하는데 이를 위해 경험 정보를 자료구조에 보관해야 합니다. 여기서 ..

10.3.2 깊이 우선 탐색(인접 행렬) 구현 이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다. 깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다. 그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요. 다음은 스택을 이용한 깊이 우선 탐색 알고리즘의..

10.3 인접 행렬을 이용한 깊이 우선 탐색 깊이 우선 탐색(Depth First Search)은 그래프의 한 정점에서 다른 정점으로 갈 수 있는 경로를 찾는 방법 중에 하나입니다. 하나의 정점에서 갈 수 있는 이웃 정점을 방문하고 다시 방문한 정점에서 이웃 정점을 방문하면서 원하는 목적 지점까지 방문하는 방법이예요. 이 때 방문했었던 정점을 다시 방문하지 말아야 합니다. 깊이 우선 탐색처럼 그래프에서 어떠한 문제를 해결하기 위해서는 그래프를 먼저 표현할 수 있어야 합니다. 정점의 개수가 비교적 적을 때는 인접행렬로 표현할 수 있습니다. 만약 정점의 개수가 많다면 인접 행렬은 이웃하지 않는 간선을 위한 영역도 포함하여 메모리 및 성능이 나빠집니다. 이럴 때는 정점과 간선의 집합으로 그래프를 표현하여 문제..