매일 조금씩

그래프 (DFS, BFS) 의 개념과 특징 본문

알고리즘/** 개념 **

그래프 (DFS, BFS) 의 개념과 특징

mezo 2024. 10. 13. 16:35
728x90
반응형

 

1. DFS (깊이 우선 탐색)

DFS는 그래프의 한 방향으로 깊이 들어가서 탐색을 마친 후, 돌아와서 다른 경로를 탐색하는 방식이다.

Java에서는 주로 재귀 호출이나 스택 자료구조를 사용하여 구현한다.

  • 시간복잡도 : O(V+E) (V: 노드 수, E: 간선 수)

DFS 예제 코드 (Java)

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GraphTraversal {

    private Map<Integer, List<Integer>> graph;

    public GraphTraversal(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
    }

    // DFS 메서드
    public void dfs(int start, Set<Integer> visited) {
        // 현재 노드를 방문 처리
        visited.add(start);
        System.out.print(start + " ");

        // 인접 노드들을 탐색
        for (int neighbor : graph.get(start)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        // 그래프 초기화 코드 추가

        GraphTraversal traversal = new GraphTraversal(graph);
        Set<Integer> visited = new HashSet<>();
        
        // DFS 탐색 시작
        traversal.dfs(0, visited);  // 시작 노드를 0으로 가정
    }
}

 

설명:

  1. dfs 메서드는 시작 노드와 방문한 노드들을 저장할 visited Set을 매개변수로 받음.
  2. 시작 노드를 방문하고 visited에 추가함.
  3. 시작 노드와 인접한 노드들을 재귀적으로 탐색함.
  4. 방문하지 않은 노드가 있다면 재귀 호출을 통해 해당 노드를 방문함.

적합한 문제 유형

  • 경로 추적 및 경로 존재 여부 확인:
    • 시작 노드에서 특정 목표 노드까지의 경로나 연결된 모든 노드를 찾는 문제에 적합하다.
    • 예시: 미로 찾기 문제나 두 노드 간 연결 여부를 확인하는 문제.
  • 백트래킹을 활용한 문제:
    • DFS의 재귀적 특성은 백트래킹 문제에 적합하다. 예를 들어 특정 경로를 탐색하다가 조건에 맞지 않으면 다시 돌아가서 다른 경로를 시도할 수 있다.
    • 예시: 퍼즐 문제, 수열이나 조합 찾기 문제, N-Queen 문제 등.
  • 사이클 탐색:
    • 그래프에서 사이클이 존재하는지 확인하는 문제에서 DFS는 간단하게 사이클을 찾을 수 있다.
    • 예시: 방향 그래프에서 사이클 검출 문제.
  • 연결된 컴포넌트 탐색:
    • 그래프의 연결 요소를 탐색하는 문제에 적합하다. DFS를 이용해 한 연결 요소를 모두 방문하고 나면, 다음 연결 요소를 탐색할 수 있다.
    • 예시: 섬의 개수를 세는 문제 (지도가 그래프 형태로 표현될 때), 강이나 호수를 구분하는 문제.
  • 자원 절약이 필요한 경우:
    • BFS보다 상대적으로 메모리를 적게 사용하므로, 큰 그래프에서 특정 경로를 찾을 때 유리할 수 있다.

즉,  최단거리/시간과 관계없이 목적지점까지 도달 가능 여부를 파악하거나, 연결된 끝까지 탐색하고 나오는 문제에 적합하다. 

 

 


2. BFS (너비 우선 탐색)

BFS는 시작점과 가까운 노드들을 먼저 탐색하고, 그 다음 레벨로 내려가면서 탐색을 진행하는 방식이다.

Java에서는 큐(Queue) 자료구조를 사용하여 구현한다. 구현체로는 LinkedList 혹은 PriorityQueue 를 목적에 맞게 사용한다.

  • 시간복잡도 : O(V+E) (V: 노드 수, E: 간선 수)

BFS 예제 문제 (Java)

import java.util.*;

public class GraphTraversal {

    private Map<Integer, List<Integer>> graph;

    public GraphTraversal(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
    }

    // BFS 메서드
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // 인접 노드 탐색
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        // 그래프 초기화 코드 추가

        GraphTraversal traversal = new GraphTraversal(graph);
        
        // BFS 탐색 시작
        traversal.bfs(0);  // 시작 노드를 0으로 가정
    }
}

 

설명:

  1. bfs 메서드는 시작 노드에서부터 탐색을 시작함.
  2. Queue를 사용해 현재 방문할 노드를 저장하고, visited Set에 방문 기록을 남김.
  3. 큐에서 노드를 하나씩 꺼내며 인접 노드를 차례대로 큐에 넣고, 방문하지 않은 인접 노드만 큐에 추가함.
  4. 큐가 빌 때까지 탐색을 계속함.

적합한 문제 유형

  • 최단 경로 탐색:
    • 모든 간선의 가중치가 동일할 때 시작 노드에서 특정 목표 노드까지의 최단 경로를 찾는 문제에 적합하다.
    • 예시: 미로 탈출 문제, 최소 이동 횟수를 찾는 문제, 두 노드 간 최소 단계수를 구하는 문제.
  • 단계별 확장 문제:
    • 문제의 해답이 여러 단계에 걸쳐 확장되는 경우에 유리하다. 탐색의 모든 노드를 차례대로 탐색하면서 각 단계별로 확장할 수 있다.
    • 예시: 네트워크의 모든 노드가 몇 단계만에 연결되는지 찾는 문제, 특정 거리 내의 노드를 찾는 문제.
  • 레벨별 탐색이 필요한 문제:
    • 노드를 레벨별로 방문하면서 각 레벨에서 해야 할 작업이 있는 문제에 적합하다.
    • 예시: 트리의 각 레벨별로 노드를 방문하는 문제 (레벨 오더 트래버설).
  • 큐 구조가 유리한 문제:
    • 탐색 노드가 순차적으로 진행되며, 이전에 방문했던 노드를 다시 방문하지 않는 문제에서 효율적이다.
    • 예시: 특정 조건을 만족하는 모든 노드를 탐색하는 문제.
  • 자원이 충분할 때:
    • BFS는 큐를 이용해 너비 우선 탐색을 진행하기 때문에 메모리를 많이 사용한다. 따라서 큰 그래프에서 메모리 제한이 없는 경우에 효과적이다.

즉, 최단 경로를 구하거나, 시작점이 여러곳이 경우 적합하다.


※ 관련 문제

[DFS]

https://gimmesome.tistory.com/267

 

Leet code (Medium) : 1466. Reorder Routes to Make All Paths Lead to the City Zero (DFS) - JAVA

방향성이 있는 그래프에서 진입차수 배열에 주어진 방향의 반대방향도 넣어두는 것이 포인트이다.다만 이 반대방향이 주어진 방향을 뒤집은 방향이라는 것을 알게 하기 위해 음수로 저장했다.

gimmesome.tistory.com

 

https://gimmesome.tistory.com/268

 

Leet code (Medium) : 399. Evaluate Division (DFS) - JAVA

이 문제도 방향성이 있는 그래프 문제와 다름이 없다. 노드간 방향성이 있는 그래프로 그려보면..각 방향은 곱으로 이어질수 있고, 기존 방향과 반대 방향의 가중치는 진입 차수 배열에 1/(가중

gimmesome.tistory.com

[BFS]

https://gimmesome.tistory.com/265

 

Leet code (Medium) : 207. Course Schedule (BFS) - JAVA

특정과목을 수강하려면 선행과목을 수강해야 할수있는데. 주어진 모든 과목을 수강할 수 있는지 확인하는 문제다.이문제는 dfs, bfs 둘 다 풀수 있으나, bfs가 좀 더 효율적이고 직관적이다. 맨처

gimmesome.tistory.com

 

https://gimmesome.tistory.com/269

 

Leet code (Medium) : 1926. Nearest Exit from Entrance in Maze (BFS) - JAVA

BFS의 대표적인 유형중 하나인, 빠른 탈출 문제이다.메모리 효율을 위해 visited 객체를 따로 생성해서 쓰지않고 방문한 곳은 주어진 그래프에서 값을 업데이트 하는 방식으로 했다. class Solution { p

gimmesome.tistory.com

 

https://gimmesome.tistory.com/270

 

Leet code (Medium) : 994. Rotting Oranges (BFS) - JAVA

BFS의 대표적인 문제유형 중 하나인, 감염 문제이다.메모리 효율을 위해 visited 객체를 따로 생성해서 쓰지않고 방문한 곳은 주어진 그래프에서 값을 업데이트 하는 방식으로 했다. 이미 썩은 오

gimmesome.tistory.com

 

 


문제를 풀면서 찾아본 것들

 

DFS에 재귀?스택?

그래프가 노드가 아닌 그리드로 주어지고 최소 1000x1000 이상이라면 재귀보단 스택을 사용하는 것이 메모리 낭비가 더 적다.

 

visited를 꼭 써야할까?

아닌 경우도 있다.

원본 자료구조가 변형되어도 상관없는 경우, 감염 확산 문제처럼 이미 방문한 곳인지 여부가 중요한 경우,

visited를 별도로 두지 않고 원본 데이터를 업데이트하며 진행하면 메모리가 절약된다.

 

visited의 자료구조는 배열? Set?

그리드에서 visited를 이차원 배열로 쓰게 되면 메모리를 너무 잡아먹어서 memory limit proceeded 가 발생할수 있으므로,

visited 는 Set을 쓰는 것이 좋다.

 

Arrays.sort()의 시간 복잡도?

O(N log N)이다. 비교 기반 정렬의 이론적 한계 때문에, 일반적인 정렬 알고리즘의 시간 복잡도는 O(N log N)이다.

N log N중에 log NN이 배열의 길이이고, 배열을 둘로 쪼개면서 비교탐색하는데 쪼개진 배열의 길이가 1이 될때까지 지속하므로

배열의 길이인 N이 2의 몇승이냐~ 와 같은 개념이라 log N이다. 

 

HashSet의 특징은?

HashSet은 값을 해시 테이블에 넣을 때, 해싱 함수로 값의 해시코드를 계산하고, 해시코드를 인덱스값으로 하는 해시테이블의 버킷에 값을 저장한다.

 

HashSet.contains()의 시간 복잡도?

contains()를 사용하면 해당값의 해시코드를 계산해서 그 값에 따라 버킷의 위치로 가서 그곳에 값이 있는지 확인하므로

시간 복잡도는 O(1)이다.

 

해시테이블의 버킷은 뭘까?

특정값이 해싱으로 인해 해시코드가 계산 될 것이다.

예를 들어, 키 "apple"이 있다면, 해시 함수는 이를 hash("apple") = 5로 변환해 5라는 해시 코드를 생성한다.

해시 테이블에서 이 값은 주소로 사용되어, 버킷 인덱스 5에 데이터를 저장하거나 인덱스 5를 바로 찾아 값을 검색하게 된다.

이렇게 해시 코드가 버킷의 주소로 사용되면서 해시 테이블에서 데이터를 효율적으로 저장하고 검색할 수 있게 된다.

해시 테이블은 해시 코드가 주소 역할을 하므로 빠른 접근이 가능하고, 해시 충돌 시에는 적절한 충돌 해결 방법으로 이를 처리하여 저장소를 효율적으로 관리한다.

 

버킷엔 하나의 값이 저장되나?

해시 테이블의 버킷에는 보통 하나의 값이 저장되도록 설계된다. 그러나 해시 테이블에서 같은 해시 코드가 발생하는 해시 충돌(hash collision)이 발생하면, 하나의 버킷에 여러 개의 값이 저장될 수 있다.

 

해시충돌이 발생하면 어떻게 해결하지?

  • 체이닝(Chaining):
    • 가장 흔한 방법으로, 버킷 자체를 연결 리스트처럼 사용하여 같은 해시 코드로 충돌된 값을 버킷에 연결된 리스트 형태로 저장한다.
    • 예를 들어, 두 개의 키가 hashTable[3] 버킷에 매핑되었다면 hashTable[3]에는 두 키-값 쌍이 리스트로 연결되어 저장된다.
  • 개방 주소법(Open Addressing):
    • 버킷에 공간이 없다면, 다른 빈 버킷을 찾아서 저장하는 방법이다.
    • 대표적인 방식으로는 선형 탐사(Linear Probing), 이중 해싱(Double Hashing) 등이 있으며, 충돌이 발생할 때 일정한 규칙에 따라 다른 버킷을 찾아간다.

 

java 에서 이 충돌방지를 어떻게 구현하면 될까?

java의 HashSet, HashMap은 자동으로 충돌관리를 해준다. HashSet은 내부적으로 HashMap을 사용하여 구현되어 있기 때문에, 해시 충돌이 발생하더라도 내부적으로 체이닝 또는 개방 주소법 같은 충돌 해결 방식을 통해 중복을 관리한다.

 

Stack 객체는 메모리 누수의 주범?

Stack 객체는 java 에서 메모리 해제가 되지 않을 수 있는 대표적인 객체 중 하나다.

pop()을 해도 값이 남아있거나, 참조가 남아있는 경우 메모리는 이를 해제하지 않아서 메모리 누수가 발생한다.

이를 방지하기 위해서, 마지막 pop() 후 명시적으로 null을 넣어주는 것이 가장 좋다.

혹은, 비슷한 구조인 ArrayDeque를 사용하는 것이 메모리 관리 측면에서 더 바람직하다.

 

java 의 인자전달 방식은?

java에선 참조 전달값 전달이있다. 

기본형 데이터 타입인 int, float, double, boolean 등은 값을 그대로 복사하여 전달한다.

참조형 데이터 타입인 Object, String, Array, List 등은 변수에 저장된 객체의 주소(참조값)를 복사하여 전달한다.

728x90
반응형