일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 리소스모니터링
- javascript
- BFS
- dfs
- deque
- Properties
- CSS
- NIO
- string
- Union-find
- priority_queue
- alter
- math
- scanner
- 큐
- sql
- GC로그수집
- map
- spring boot
- 스프링부트
- union_find
- Java
- 스택
- date
- set
- List
- JPA
- 힙덤프
- html
- Calendar
- Today
- Total
매일 조금씩
그래프 (DFS, BFS) 의 개념과 특징 본문
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으로 가정
}
}
설명:
- dfs 메서드는 시작 노드와 방문한 노드들을 저장할 visited Set을 매개변수로 받음.
- 시작 노드를 방문하고 visited에 추가함.
- 시작 노드와 인접한 노드들을 재귀적으로 탐색함.
- 방문하지 않은 노드가 있다면 재귀 호출을 통해 해당 노드를 방문함.
적합한 문제 유형
- 경로 추적 및 경로 존재 여부 확인:
- 시작 노드에서 특정 목표 노드까지의 경로나 연결된 모든 노드를 찾는 문제에 적합하다.
- 예시: 미로 찾기 문제나 두 노드 간 연결 여부를 확인하는 문제.
- 백트래킹을 활용한 문제:
- 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으로 가정
}
}
설명:
- bfs 메서드는 시작 노드에서부터 탐색을 시작함.
- Queue를 사용해 현재 방문할 노드를 저장하고, visited Set에 방문 기록을 남김.
- 큐에서 노드를 하나씩 꺼내며 인접 노드를 차례대로 큐에 넣고, 방문하지 않은 인접 노드만 큐에 추가함.
- 큐가 빌 때까지 탐색을 계속함.
적합한 문제 유형
- 최단 경로 탐색:
- 모든 간선의 가중치가 동일할 때 시작 노드에서 특정 목표 노드까지의 최단 경로를 찾는 문제에 적합하다.
- 예시: 미로 탈출 문제, 최소 이동 횟수를 찾는 문제, 두 노드 간 최소 단계수를 구하는 문제.
- 단계별 확장 문제:
- 문제의 해답이 여러 단계에 걸쳐 확장되는 경우에 유리하다. 탐색의 모든 노드를 차례대로 탐색하면서 각 단계별로 확장할 수 있다.
- 예시: 네트워크의 모든 노드가 몇 단계만에 연결되는지 찾는 문제, 특정 거리 내의 노드를 찾는 문제.
- 레벨별 탐색이 필요한 문제:
- 노드를 레벨별로 방문하면서 각 레벨에서 해야 할 작업이 있는 문제에 적합하다.
- 예시: 트리의 각 레벨별로 노드를 방문하는 문제 (레벨 오더 트래버설).
- 큐 구조가 유리한 문제:
- 탐색 노드가 순차적으로 진행되며, 이전에 방문했던 노드를 다시 방문하지 않는 문제에서 효율적이다.
- 예시: 특정 조건을 만족하는 모든 노드를 탐색하는 문제.
- 자원이 충분할 때:
- BFS는 큐를 이용해 너비 우선 탐색을 진행하기 때문에 메모리를 많이 사용한다. 따라서 큰 그래프에서 메모리 제한이 없는 경우에 효과적이다.
즉, 최단 경로를 구하거나, 시작점이 여러곳이 경우 적합하다.
※ 관련 문제
[DFS]
https://gimmesome.tistory.com/267
https://gimmesome.tistory.com/268
[BFS]
https://gimmesome.tistory.com/265
https://gimmesome.tistory.com/269
https://gimmesome.tistory.com/270
문제를 풀면서 찾아본 것들
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 N은 N이 배열의 길이이고, 배열을 둘로 쪼개면서 비교탐색하는데 쪼개진 배열의 길이가 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 등은 변수에 저장된 객체의 주소(참조값)를 복사하여 전달한다.
'알고리즘 > ** 개념 **' 카테고리의 다른 글
LinkedList 개념과 특징 (0) | 2024.10.21 |
---|---|
Interval 개념 및 특징 (0) | 2024.10.16 |
DP의 개념과 특징 (0) | 2024.10.06 |
최단경로 알고리즘(2) - 플로이드 워셜 (0) | 2021.05.16 |
최단경로 알고리즘(1) - 다익스트라 (0) | 2021.05.16 |