🌻 JAVA/알고리즘, 자료구조

알고리즘 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

2020. 12. 21. 11:26
목차
  1. BFS (너비 우선 탐색)
  2. BFS 구현
  3. DFS (깊이 우선 탐색)
  4. 📄 REFERENCES
반응형

BFS (너비 우선 탐색)


BFS의 장점

  • 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
  • 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름
  • 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
  • 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

BFS의 단점

  • 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
  • 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

BFS 구현

Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다.

  1. Queue에서 하나의 노드를 꺼냅니다.
  2. 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다.
/* BFS 코드 구현 */
public void bfs(Node root) {
    Queue<Node> qu = new LinkedList<Node>();
    Node temp = root;
    qu.add(temp);

    while(!qu.isEmpty()){
    
        /* 큐에서 뽑아서 바로 출력 시킨다. */
        temp = qu.poll();
        System.out.println(temp.value + " -> ");

        if(temp.left != null)	// temp.left가 있으면 큐에 추가.
            qu.add(temp.left);
        if(temp.right != null)
            qu.add(temp.right);	// temp.right가 있으면 큐에 추가.
    }
}

 

더보기

boolean 배열 visit로 해당 노드의 왼쪽, 오른쪽 노드를 방문했는지 체크 하면서 탐색하는 방법도 있다.

/* 내가 짠 코드 */
public void bfs(Node node) {
        Queue<Node>  qu = new LinkedList<Node>();
        boolean[] visit = {false,false};
        Node temp = this.root;
        qu.add(temp);

        while(!qu.isEmpty()){
            temp = qu.peek(); // qu에서 하나를 뽑는다.

            if(!visit[0]){
                if(temp.left != null) {
                    qu.add(temp.left);
                    visit[0] = true;
                }else{
                    System.out.print(qu.poll().value + " -> ");
                }
            }else if(!visit[1]){
                if(temp.right != null) {
                    qu.add(temp.right);
                    visit[1] = true;
                }else{
                    System.out.print(qu.poll().value + " -> ");
                }
            }else if(visit[0] && visit[1]){
                visit[0] = false;
                visit[1] = false;
                System.out.print(qu.poll().value + " -> ");
                temp = qu.peek();
            }
        }
    }

 

DFS (깊이 우선 탐색)


DFS의 장점

  • 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있는 경우 빠르게 구할 수 있다.
  • 구현이 너비 우선 탐색(BFS) 보다 간단하다.

DFS의 단점

  • 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느리다.
  • 결과 값이 없는 경로에 깊이 빠질 가능성이 있다.

DFS 코드 구현

  • 중위순회(In-order) 방식과 동일
/* DFS 코드 구현 */
public void dfs(Node node) {
    if(node != null) {
        dfs(node.left);
        System.out.println(node.value + " -> ");
        dfs(node.right);
    }
}

📄 REFERENCES


coding-factory.tistory.com/611?category=794828

coding-factory.tistory.com/612

www.notion.so/Live-Study-5-75f857b63e524d33914a8b3ec6e1e894

coding-factory.tistory.com/612

반응형
저작자표시 (새창열림)
  1. BFS (너비 우선 탐색)
  2. BFS 구현
  3. DFS (깊이 우선 탐색)
  4. 📄 REFERENCES
'🌻 JAVA/알고리즘, 자료구조' 카테고리의 다른 글
  • 알고리즘 - 퀵 정렬 (Quick-Sort)
  • 자료구조 - 이진탐색 트리 (Binary-Search-Tree)
  • 알고리즘 - 백트래킹(Back-Tracking)
  • 알고리즘 - 재귀 알고리즘 (feat. Factorial, Fibonacci)
iseunghan
iseunghan
꾸준하게 열심히..
iseunghan
iseunghan

공지사항

  • 어제보다 나은 오늘이 되기 위해 🔥
  • 분류 전체보기 (262)
    • 💐 Spring (14)
      • 개념 및 이해 (2)
      • Spring 핵심 기술 (24)
      • Spring REST API (8)
      • Spring MVC, DB 접근 기술 (7)
      • Spring Security (23)
      • Spring in Action (1)
    • 🌻 JAVA (84)
      • 자바 ORM 표준 JPA 프로그래밍 (20)
      • 알고리즘, 자료구조 (13)
      • 디자인 패턴 (7)
      • 정리정리정리 (43)
      • JUnit (1)
    • 🔖 Snippets (3)
      • Javascript (3)
    • ⚙️ Devops (22)
      • ⛏ Git (11)
      • 🐳 Docker (6)
      • 🐧 Linux (3)
      • 🌈 Jenkins (1)
      • 📬 Kafka (1)
    • 💬 ETC.. (4)
      • 💻 macOS (2)
    • 🌧️ ORM (2)
      • JPA (2)
    • 🐍 Python (3)
    • 📚 Databases (15)
      • 오라클로 배우는 데이터베이스 개론과 실습(2판) (3)
      • RealMySQL 8.0 (8)
    • 🔥 Computer Science (5)
      • 📡 네트워크 (5)
    • 🏷️ 협업 (1)
    • 📜 코딩테스트 (38)
      • BAEKJOON\수학 1, 수학 2 (8)
      • BAEKJOON\재귀 (5)
      • BAEKJOON\브루트 포스 (3)
      • BAEKJOON\정렬 (1)
      • BAEKJOON\백트래킹 (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\이분탐색 (1)
      • BAEKJOON\다이나믹 프로그래밍 (9)
      • BAEKJOON\그리디 알고리즘 (0)
    • ✨ ISEUNGHAN (1)

인기 글

전체
오늘
어제
반응형
hELLO · Designed By 정상우.
iseunghan
알고리즘 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.