그래프 탐색 알고리즘
배운점
너비 우선 탐색(BFS, Breadth First Search)
인접한 정점부터 방문하는 탐색 방식
너비 우선 탐색의 특징
- 최단 경로 탐색에 유리하다(같은 거리에 있는 정점들을 먼저 방문한다)
- 방문한 정점들을 저장해야 하는 경우 메모리 사용이 크다
- 그래프의 크기와 밀도가 크면 BFS의 성능이 저하된다
- 시작 정점에서 도착할 수 없는 정점에 대해서는 탐색하지 않는다
- 방문 여부를 체크하는 자료구조를 사용해야한다(무한 루프 방지)
구현 방법
- 큐 자료구조를 활용해 구현된다
- 시작 노드를 큐에 삽인한 후, 큐가 빌 때까지 반복한다
- 큐에서 현재 정점을 가져온다
- 현재 정점은 이미 방문했다고 체크한다
- 현재 정점에 인접한 정점을 모두 큐에 삽입힌다
- 큐가 빌 때까지 반복한다
BFS를 활용해야 하는 경우
- 최단 거리를 구해야 하는 문제
- 검색 대상의 규모가 크지 않고, 시작 정점으로 부터 멀지 않을 경우
한 경로가 무한히 이어진다 해도, 모든 경로를 확인하기에 반드시 최단 경로를 찾을 수 있다
BFS 활용 시 주의 할 점
- 방문 여부 체크
- 큐의 활용
- 최단 경로 탐색
- 메모리 공간(메모리를 많이 사용한다)
BFS 예시 구현
public ArrayList<Integer> bfs_array(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
//bfs의 경우 큐를 사용합니다.
Queue<Integer> queue = new LinkedList<>();
//시작 지점을 큐에 넣어주고, 해당 버택스의 방문 여부를 변경합니다.
queue.offer(src);
visited[src] = true;
//큐에 더이상 방문할 요소가 없을 경우까지 반복합니다.
while (!queue.isEmpty()) {
//현재 위치를 큐에서 꺼낸 후
int cur = queue.poll();
// 현재 방문한 정점을 result에 삽입합니다.
result.add(cur);
//전체 배열에서 현재 버택스의 행만 확인합니다.
for (int i = 0; i < array[cur].length; i++) {
//길이 존재하고, 아직 방문하지 않았을 경우
if(array[cur][i] == 1 && !visited[i]) {
//큐에 해당 버택스의 위치를 넣어준 이후
queue.offer(i);
//방문 여부를 체크합니다.
visited[i] = true;
}
}
}
//이어진 모든 길을 순회한 후 방문 여부가 담긴 ArrayList를 반환합니다.
return result;
}
깊이 우선 탐색(DFS, Depth First Search)
시작 정점에서 최대한 깊숙이 탐색하고, 다음 분기로 탐색을 진행하는 탐색 방식
깊이 우선 탐색의 특징
- 한 분기를 완벽하게 탐색한 후, 다음 분기로 넘어간다
- 더 이상 탐색이 불가능한 상태가 되면 이전 분기로 돌아와 다음 분기를 탐색한다
- 그래프 내 순환구조(Cycle)를 고려하여 방문한 정점은 다시 방문하지 않도록 한다
구현 방법
- 스택이나 재귀를 통해 구현한다(재귀 구현 권장)
- 방문했던 정점인지 확인한다. 방문 했다면 재귀 호출을 종료한다
- 방문하지 않았다면, 방문 여부를 체크한다
- 해당 정점에 연결된 모든 정점을 재귀호출로 순회한다
DFS를 활용해야 하는 경우
- 경로의 특징을 저장해야 하는 문제(탐색중에 조건이 요구되는 경우)
- 자동 미로 생겅 같은 문제(하나의 경로만 구할 수 있다)
- 검색 대상 그래프가 정말 클 때(BFS에 비해 메모리를 적게 사용한다)
DFS 활용 시 주의할 점
- 순환구조를 고려하여 방문한 정점은 다시 방문하지 말아야한다
- 최단 경로를 보장 할 수 없다
DFS 예시 구현
public ArrayList<Integer> dfs(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
// 이미 방문했다면
if (visited[src] == true) {
result.add(src); // 방문한 정점을 저장
return result; // 저장한 데이터를 반환하며, 재귀호출을 종료
}
// 아직 방문하지 않았다면
visited[src] = true; // 방문한 정점을 표기
// 현재 정점에서 이동할 수 있는 정점을 순회하며 재귀 호출
for (int index = 0; index < array.length; index++) {
if (array[src][index] == 1) {
// 재귀 호출을 통해, 방문 여부를 담은 데이터를 반환과 동시에 할당
result = dfs(array, visited, index, result);
}
}
return result;
}
느낀점
오늘은 그래프에 대해 공부했다!
1년 6개월 만에 다시 그래프를 공부하니까 역시 쉽지 않다는 생각이 들었다.
일차원 배열 형식의 구조에 익숙해서 그런지
이차원 배열 형식의 문제를 풀 때 자주 뇌정지가 온다,,
그리고 아직 재귀적 사고도 익숙하지 않아서 흐름을 잡는게 쉽지 않은 것 같다
하지만 내가 아직 이차원 배열, 재귀, 그래프에 관한 사고방식이 미숙하기 때문이라고 생각하고,
계속 풀다보면 어느 순간부터 흐름을 잡을 수 있다고 믿고 있다!!
댓글남기기