알고리즘 - search - dfs&bfs
문제는 자바를 이용해 풀어보겠습니다!
들어가며
이번 포스트에서는 탐색 기법에 대한 이야기를 해보려고 합니다.
알고리즘은 공부를 하면 할 수록 더욱 깊고 , 다양한 조합을 만들 수 있기 때문에 기본적이며 핵심적인 이야기들을 위주로 공부해본 내용을 정리하겠습니다.
DFS - 깊이 우선 탐색
DFS : depth first search 는 완전 탐색 기법 중 하나 입니다.
완전 탐색 기법 (Exhaustive Search) 은 모든 경우의 수를 탐색해 해를 찾는 기법입니다.
특징은 일관되고 , 간단하고 직관적입니다.
당연히 모든 경우의 수를 탐색하는 만큼 경우의 수가 많아질 수 록 효율이 낮아집니다.
| 기능 | 특징 | 시간 복잡도 |
|---|---|---|
| 그래프 완전 탐색 | 재귀 함수를 사용 | O(V+E) |
| 스택 자료구조 이용 | V : node의 수 , E : 에지 수 |
재귀 함수를 사용한다. (구현 할때 재귀함수 사용함)
결국 자기 자신을 부르는 구조로 구현이 되기 때문에 스택 오버 플로우가 발생할 가능성이 존재합니다. 이점을 유의 하면서 코딩 해야 합니다.
구현 하는 원리는 다음과 같습니다.
처음 초기화를 하며 시작점을 선택합니다.
또한, 방문한 기록을 저장하기 위한 배열을 생성 & 그래프 데이터를 저장할 인접 리스트를 생성
Stack의 시작점에 대한 노드를 삽입합니다.
이후 노드를 꺼내고 해당 노드와 연결된 노드를 Stack에 삽입합니다.
그리고 이것을 반복하면 DFS의 탐색 순서를 얻을 수 있고 , 구현이 가능합니다.
BFS - 너비 우선 탐색
BFS: breadth-frist-search 너비 우선 탐색
시작 노드 기준으로 가까운 노드를 먼저 방문한다.
BFS는 큐를 이용해 구현합니다.
| 기능 | 특징 | 시간 복잡도 |
|---|---|---|
| 그래프 완전 탐색 | FIFO를 사용 | O(V+E) |
| Queue 자료구조 이용 | V : node의 수 , E : 에지 수 |
구현원리는 다음과 같습니다.
- 시작점을 선택하고 초기화 합니다. 여기서 데이터를 저장해둡니다.
큐에 삽입한 노드를 pull 하고 관련된 노드 즉,인접한 노드를 큐에삽입합니다
-여기서 유의할 점은 큐에 삽입했다고 아직 방문한 상태는아닙니다.
- 모든 경우의 수를 만족할때까지반복합니다.
구현해보자
잘 생각하면 dfs와 bfs 둘다 인접리스트와 방문배열을 사용합니다.
그리고 구분점은 Stack의 LIFO , Queue의 FIFO를 활용하는지에 따라 두 방법의 구분이 가능합니다.
그럼 자바로 예시코드를 보면서 이야기해보겠습니다.
백준 -1260 문제입니다.
위 언급하였듯이 두 search 알고리즘은 인접리스트와 방문배열을 사용합니다.
1
2
static ArrayList<Integer>[] dataArr;
static boolean[] visted;
자바에서는 이런식으로 구현할 수 있습니다.
ArrayList로 이루어진 배열을 선언함으로써 인접리스트를 구현할 수 있습니다.
방문배열은 boolean형 배열을 선언함으로써 구현할 수 있습니다.
ArrayList?
자주 사용하는데 굳이 의미를 두고 쓰지 않아 설명해보려니 햇갈려서 정리하였습니다.
ArrayList는 자바에서 제공하는 동적 배열(dynamic array)로, 크기가 가변적으로 자동으로 조절되는 배열입니다. 기존의 배열과는 달리, 요소를 추가하거나 삭제할 때 크기 조절이 자동으로 이루어져 편리하게 사용할 수 있습니다.
특징
- 가변 크기: 배열의 크기를 동적으로 조절할 수 있습니다. 요소를 추가하면 자동으로 크기가 증가하고, 요소를 삭제하면 자동으로 크기가 감소합니다.
- 인덱스 기반 접근: 각 요소는 인덱스를 사용하여 접근할 수 있습니다. ArrayList는 내부적으로 배열을 사용하기 때문에 인덱스를 통한 접근이 빠릅니다.
- 제네릭 타입 지원: 제네릭 타입을 사용하여 저장될 요소의 타입을 명시할 수 있습니다. 이를 통해 타입 안정성을 보장하고 형 변환을 줄일 수 있습니다.
- 배열과 유사한 성능: 요소의 추가나 삭제 시 배열을 복사하는 과정이 필요하지만, ArrayList는 배열을 사용하기 때문에 배열과 유사한 성능을 보입니다.
초기화하기
1
2
3
4
5
6
dataArr = new ArrayList[n+1];
visted = new boolean[n+1];
for(int i=1; i<n+1; i++){
dataArr[i] = new ArrayList<>();
}
공부하면서 +1이 왜필요할지에 대해서 생각을 해봤습니다.
그래프에서 정점을 0을 안쓰니까 즉, 보통 정점을 1부터 시작하는 정수로 사용하기 때문에 0을 비워두고 쓰기 때문이다. 라고 생각 해봤는데 일단 bard도 이런식으로 답변해서 맞는 이유라고 생각합니다.
방향에 대하여
1
2
3
4
5
6
7
8
for(int i =0; i<m; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
dataArr[a].add(b);
dataArr[b].add(a);
}
만약 양뱡향 , 무뱡향인 경우에는 양쪽 모두를 넣어줘야합니다.
하지만 한쪽방향이 지정 된 경우에는 한쪽만 넣어주면 됩니다.
DFS - 재귀함수를 이용해 구현하기
1
2
3
4
5
6
7
private static void _dfs(int node){
System.out.print(node + " ");
visted[node] =true;
for(int i : dataArr[node]){
if(! visted[i]) bfs_01_dfs(i);
}
}
위에 선언해 뒀던 인접리스트 배열에서 값을 뽑은다음
방문 기록을 확인해 방문하지 않은 부분을 재귀 하면 됩니다.
DFS - Stack으로 구현하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Stack<Integer> stack = new Stack<>(); // 스택 생성
stack.push(start); // 시작 정점을 스택에 넣음
visited[start] = true; // 시작 정점 방문 표시
System.out.println("DFS 결과:");
while (!stack.isEmpty()) {
int current = stack.pop(); // 스택에서 정점을 꺼냄
System.out.print(current + " "); // 현재 정점 출력
// 현재 정점과 연결된 정점들 중 방문하지 않은 정점을 스택에 넣음
for (int next : dataArr[current]) {
if (!visited[next]) {
stack.push(next);
visited[next] = true;
}
}
}
stack을 선언한 뒤 시작점을 push하고
stack의 값이 없을때까지 pop하여 해당 값이 방문하지 않은경우 push 해주면 됩니다.
BFS - Queue를 이용해 구현하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void _bfs(int node){
visted[node] =true;
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()){
int now = queue.poll();
System.out.print(now + " ");
for(int i : dataArr[now]){
if(! visted[i]){
visted[i] =true;
queue.add(i);
}
}
}
}
Queue를 선언하고 들어온 큐를 삽입합니다 .(시작점)
Queue가 빌때까지 반복하며 현재 값을 poll합니다. 그리고 이 값이 방문하지 않은 경우에는
Queue에 추가하면 됩니다.
정리하며
이번 포스트 에서는 DFS와 BFS에 대해 정리해봤습니다.