트리에서 DFS, BFS로 값 찾기

깃허브
DFS, BFS
비교
코드(DFS)
값을 찾는 과정

깃허브

깃허브

DFS, BFS

DFS
깊이 우선 탐색으로 한 가지에서 일어날 수 있는 모든 가지들 중에 한 곳만 깊게 파고들어가 값을 찾고 없으면 하나씩 가지를 클리어 해가는 방식의 탐색 알고리즘이다.

BFS
너비 우선 탐색으로 한 가지에서 일어날 수 있는 모든 가지들을 하나씩 확인해 가며 값을 찾는 탐색 알고리즘이다.

비교

DFS의 장단점

• 장점
  1. 비교적 쉽게 구현할 수 있다.
  2. 단순한 구조일수록 값의 탐색이 비교적 빠르다.
• 단점
  1. 그래프 구조의 경우 최적의 경로를 보장시켜주지 않는다.
  2. 순환 구조의 그래프일 경우 무한 루프에 빠질 수 있다.

시간복잡도 : O(V+E)
공간복잡도 : O(V)
(v는 정점의 수, E는 간선의 수)

BFS의 장단점

• 장점
  1. 그래프 구조에서도 최단 경로를 보장한다.
  2. 단계별로 탐색하기 때문에 균일한 시간복잡도를 보여준다.
• 단점
  1. 메모리를 많이 사용한다. (찾는 값이 나오기 전까지 모든 가능성의 노드들을 저장하면서 진행하기 때문에)
  2. 구현이 비교적 더(그래프에서는) 복잡하다.

시간복잡도 : O(V+E)
공간복잡도 : O(V)
(v는 정점의 수, E는 간선의 수)

DFS, BFS 둘다 각 간선을 한 번씩만 탐색함으로 정점의 수 + 간선의 수 O(V+E)
둘다 스택, 큐로 구현하기 때문에 공간복잡도 또한 정점의 수O(V)

코드(DFS)

	public static <T> Tree<T> findDfs (Tree<T> root, T data) {
        LinkedList<Tree<T>> stack = new LinkedList<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            Tree<T> cur = stack.pop();
            if(cur.data.equals(data)) {
                return cur;
            }
            for(Tree children : cur.childrens) {
                stack.push(children);
            }
        }
        throw new IllegalArgumentException("찾는값 이 존재 하지 않음");
    }

따로 LinkedList를 만들어놓은 상태여서 stack처럼 사용했다.

1. stack으로 사용할 리스트 초기화

LinkedList<Tree<T>> stack = new LinkedList<>();

2. 탐색을 시작할 트리구조의 루트노드 stack에 추가(루트에서부터 탐색을 시작함을 의미)

stack.push(root);

3. 반복문이 진행되는 과정중에 stack이 비어있으면 찾는 값이 없는걸로 판단

  while(!stack.isEmpty()) {
  
  ......
  
  }

4. 가장 마지막에 stack에 push된 노드를 pop(get) 시켜서 탐색, pop을 통해 stack에서 제거(맨 처음 push했던 루트의 탐색(6)이 끝남을 의미)

Tree<T> cur = stack.pop();

5. 찾는 값과 동일한 값이 노드에서 발견되면 노드 리턴

	if(cur.data.equals(data)) {
		return cur;
	}

6. 찾는 값과 일치하지 않아서 더 깊이 값을 찾기 위해 현재 노드의 자식노드들을 stack에 push

	for(Tree children : cur.childrens) {
		stack.push(children);
    }

7. while문이 끝났다는 말은 root노드부터 하위 노드 전체를 뒤져봤지만 값을 찾지 못함을 의미하기 때문에 에러 던짐

	throw new IllegalArgumentException("찾는값 이 존재 하지 않음");

8. BFS의 경우 pop대신 shift 이용

	public static <T> Tree<T> findBfs (Tree<T> root, T data) {
        LinkedList<Tree<T>> queue = new LinkedList<>();
        queue.push(root);

        while(!queue.isEmpty()) {
            Tree<T> cur = queue.shift();
            if(cur.data.equals(data)) {
                return cur;
            }
            for(Tree children : cur.childrens) {
                queue.push(children);
            }
        }
        throw new IllegalArgumentException("찾는값 이 존재 하지 않음");
    }

트리 구조에서의 값 탐색이기 때문에 BFS와 DFS의 코드 차이가 pop과 shift차이밖에 없다.
하지만 pop의 경우 마지막으로 들어온 노드를 기준으로 파고 내려가기 때문에 한 가지의 끝까지 내려갔다가 없으면 위로 한칸 올라가서 다른 말단 가지들을 탐색하기를 반복하고
shift의 경우 쌓인 순서대로 가지를 탐색하기 때문에 루트에서 방문할 수 있는 모든 가지들을 탐색하고 찾는 값이 없으면 맨처음 자식의 가지들의 자식들을 다시 탐색하는 식의 너비 우선 탐색이 이루어진다.