![[알고리즘] 탐색 - DFS, BFS, 이진 탐색](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdzgVxf%2FbtrMIdTTC2d%2FuMEd52yzOxa1OoD1C7e6ZK%2Fimg.png)
| 탐색이란?
주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘
| 탐색의 종류
| 언제? | 특징 | 시간복잡도 | |
| DFS(깊이 우선 탐색) | 그래프의 모든 노드를 탐색하고자 할 때 |
- 재귀 또는 스택을 통해 구현 - 트리의 pre-order, in-order, post-order 순회 모두 DFS이다. |
* 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) |
| BFS(너비 우선 탐색) | 그래프의 가까운 지점부터 탐색하고자 할 때 | - 큐를 통해서 구현 - 트리의 level-order 가 BFS이다. |
* 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2) |
| 이진 탐색 |
* DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다.
1. DFS (깊이 우선 탐색)
DFS란, 루트에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
[출처] https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html- 참조한 블로그에서는 미로를 탐색하는 것을 이야기했는데, 미로의 여러 갈랫길 중 첫번째 길만 쫒아가다가 다시 돌아와(backtracking) 방문하지 않은 곳을 탐색하여, 결국 모든 곳을 가는 것을 DFS라고 했다.
- 하나의 노드 A와 인접한 노드가 B, C가 있다고 할 때 먼저 B의 분기(인접한 노드들)를 모두 마쳐야만, C를 갈 수 있다.
- 트리의 level-order을 제외한 나머지 순회들과의 차이점은 어떤 노드를 방문했는지를 방문 배열을 통해 검사한다는 것.
(1) 구현
| 스택 | 재귀 (순환 호출) |
| 1. 시작 노드 정한 후, 사용할 자료구조 초기화 - 인접 리스트로 그래프 표현 - 방문 배열 초기화 후 시작지점 true 표시 - 시작 노드를 스택에 삽입 2. 스택에서 노드 꺼낸 후 인접 노드 다시 삽입하며 방문 체크 3. 스택에 값이 없을 때까지 2를 반복 |
1. 사용할 자료구조 초기화 - 인접리스트로 그래프 표현 - 방문 배열 초기화 2. 루트 노드(=시작 노드)를 방문하여 방문 체크 3. 인접한 노드들 중 방문하지 않은 곳을 방문 4. 방문할 노드들이 없을 때까지 3를 반복 |
- 백준의 아래 문제를 통해 한 번 구현해보았다.
[1] 먼저 자료구조를 초기화한다. : 정점/간선 갯수나, 인접리스트, 방문배열은 전역으로 빼주었다.
public class Ex11724 {
static int N;
static int M;
static List<List<Integer>> graph;
static boolean[] visited;
static int cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 인접 리스트 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
// 방문 배열 초기화
visited = new boolean[N + 1];
cnt = 0;
}
}[2] 문제에서 요구하는 연결망의 갯수 구하는 코드를 넣는다.
- 이 문제는 프로그래머스의 '네트워크' 문제와도 유사했는데, 분리된 연결망을 구하는 문제였다.
> 분기를 확인하기 위한 코드
// 2. dfs
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs_stack(i);
cnt++;
}
}
System.out.println(cnt);> 예외 상황 : 노드가 하나밖에 없고 간선이 없는 경우 - 네트웍은 하나다.
// 노드가 하나밖에 없고 간선이 없어도 네트웍은 하나로 치부
if (N == 1 && M == 0) {
System.out.println(1);
return;
}[3] 본격적인 dfs를 짜기
[3-1] 재귀 방식의 dfs
public static void dfs(int root) {
// 루트 방문 체크
visited[root] = true;
// 인접한 노드들 중 방문하지 않은 곳을 방문
for (int i = 0; i < graph.get(root).size(); i++) {
int adjNode = graph.get(root).get(i);
if (!visited[adjNode]) {
dfs(adjNode);
}
}
}
[3-2] 스택 방식의 dfs
public static void dfs_stack(int start) {
Stack<Integer> stack = new Stack<>();
visited[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
int curNode = stack.pop();
for (int i = 0; i < graph.get(curNode).size(); i++) {
int adjNode = graph.get(curNode).get(i);
if (!visited[adjNode]) {
stack.push(adjNode);
visited[adjNode] = true;
}
}
}
}[ 전체 코드 - 더보기 ]
package graph;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
public class Ex11724 {
static int N;
static int M;
static List<List<Integer>> graph;
static boolean[] visited;
static int cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 1 && M == 0) {
System.out.println(1);
return;
}
// 1. 시작 노드를 정한 후 사용할 자료구조 초기화
// 인접 리스트 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
// 방문 배열 초기화
visited = new boolean[N + 1];
cnt = 0;
// 2. dfs
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs_stack(i);
cnt++;
}
}
System.out.println(cnt);
}
public static void dfs(int root) {
// 루트 방문 체크
visited[root] = true;
// 인접한 노드들 중 방문하지 않은 곳을 방문
for (int i = 0; i < graph.get(root).size(); i++) {
int adjNode = graph.get(root).get(i);
if (!visited[adjNode]) {
dfs(adjNode);
}
}
}
public static void dfs_stack(int start) {
Stack<Integer> stack = new Stack<>();
visited[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
int curNode = stack.pop();
for (int i = 0; i < graph.get(curNode).size(); i++) {
int adjNode = graph.get(curNode).get(i);
if (!visited[adjNode]) {
stack.push(adjNode);
visited[adjNode] = true;
}
}
}
}
}
(2) 시간 복잡도
- DFS는 그래프의 정점의 수(V)와 간선의 수(E)를 통해 시간 복잡도를 표현하는데,
- 인접 행렬을 사용하는 경우, 행으로는 전체 정점(V)을, 열로는 인접한 정점과의 연결 여부(E)를 확인하므로,
-- O(V^2) 의 시간 복잡도를 가진다.
- 인접 리스트를 사용하는 경우, 각 정점(V)을 방문한 후, 인접 노드를 따라 하나씩 탐색하기 때문에,
-- O(V + E)의 시간 복잡도를 가진다.
- 그래프를 완전 탐색할 때에는 따라서, 간선이 적을 때에 인접 리스트를 사용하는 것이 좋다.
2. BFS (너비 우선 탐색)
bfs란, 루트에서 시작해서 인접한 노드를 먼저 탐색하는 방법
[출처] https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html- DFS의 경우, 깊이 있게 탐색했다면, BFS는 가까운 지점을 먼저 탐색하는 "넓은" 탐색이다.
- 참고한 블로그에서는, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때에 이 방법을 쓴다고 했다.
- BFS를 활용한 알고리즘이 바로 최단 경로를 구하는 다익스트라였다.
* BFS와 차이점이 있다면, 다익스트라는 DP를 사용한다는 점..
https://why-dev.tistory.com/247?category=958869
[알고리즘] 최단 경로 구하기 - 1. 다익스트라
| 다익스트라 - 가중치가 있는 그래프에서, 최단 경로를 구하는 알고리즘 - 핵심 : 그래프의 인접리스트와 DP를 이용 - 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색 - 특징 : 간선은 모두 양
why-dev.tistory.com
- BFS는 구현 방법을 정리하기 보다, 문제를 보면서 얘기해보려고 한다.
- 아래는, 프로그래머스의 게임 맵 최단 거리를 구하는 문제이다.
https://school.programmers.co.kr/learn/courses/30/lessons/1844#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
(1) 코드
: 아래를 보면 알 수 있듯이, 게임 최단 거리를 구하는 문제는 BFS로 풀어야 했는데,
: 그 이유는 사방위로 움직여서 갈 수 있는 경로 중 도착지에 가까운 경로를 선택하려면,
깊이있는 탐색보다는 너비 탐색을 통해서 사방위중 도착지에 가까운 방향 (아래로, 우측으로)으로 먼저 탐색을 하고,
탐색한 횟수에 대해 저장하며 나아가야 했기 때문이다.
: DFS로 풀게될 경우에는 이런 탐색 횟수를 저장하며 갈 때 너무 많은 시간이 소요된다.
(왜냐면 깊이 탐색 후, 다시 제자리로 돌아와서 또 다른 갈래로 깊이 탐색 후, 또 다른 갈래로 깊이 탐색을 해야해서...)
: 그렇기에 그래프 최단 경로를 구할 때에도 BFS를 응용한 다익스트라를 사용한다.
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
class Node {
int r;
int c;
int cnt;
public Node(int x, int y, int cnt) {
this.r = x;
this.c = y;
this.cnt = cnt;
}
}
int[][] maps;
int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};
public int solution(int[][] maps) {
this.maps = maps;
return bfs(maps.length, maps[0].length);
}
public int bfs(int r, int c){
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0, 1));
maps[0][0] = 0;
while (!q.isEmpty()) {
Node cur = q.poll();
if (cur.r == r - 1 && cur.c == c - 1) {
return cur.cnt;
}
for (int[] d : dir) {
int newR = cur.r + d[0];
int newC = cur.c + d[1];
if (newR >= 0 && newC >= 0 && newR < r && newC < c) {
if (maps[newR][newC] == 1) {
maps[newR][newC] = 0;
q.add(new Node(newR, newC, cur.cnt + 1));
}
}
}
}
return -1;
}
}
[ 참고 및 출처 ]
부트캠프 수업 내용 정리
[Do it 알고리즘 코딩 테스트 - 자바 편]
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
프로그래머스
'Computer Science > Algorithm' 카테고리의 다른 글
| [알고리즘] 분할정복 (0) | 2022.08.25 |
|---|---|
| [알고리즘] 그리디 (0) | 2022.08.25 |
| HashSet<int[]>와 Hashset<ArrayList<Integer>> (0) | 2022.08.17 |
| [알고리즘] 정렬 (0) | 2022.08.11 |
| [알고리즘] 알고리즘 개요 (0) | 2022.08.09 |