Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- React
- 프로그래머스
- 백준 13023번
- 백준 2638번
- 1937번 욕심쟁이 판다
- 알고리즘 수업-깊이 우선 탐색1
- 백준
- ssh
- Redux
- 리덕스
- Java
- dfs
- 13023번 ABCDE
- 2638번 치즈
- 1389번 케빈 베이컨의 6단계 법칙
- 백준 1068번 트리
- 힙 자바스크립트
- 24480번
- 알고리즘
- 1303번
- 기지국 설치 js
- 백준 1068
- level0
- JavaScript
- 2275번
- 부녀회장이 될 테야
- level1
- 우선순위 큐 자바스크립트
- 자바스크립트
- 기지국 설치 자바스크립트
Archives
- Today
- Total
코딩왕랄프👊🏻
[알고리즘] DFS 본문
반응형
SMALL
DFS 알고리즘 (Depth-First Search , 깊이우선탐색)
특징
-루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
사용되는 상황
- 모든 노드를 방문 하고자 하는 경우
- 경로의 특징이 필요한 문제를 풀 때
알고리즘 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함
탐색 과정
구현 (Javascript)
const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "G", "H", "I"],
D: ["B", "E", "F"],
E: ["D"],
F: ["D"],
G: ["C"],
H: ["C"],
I: ["C", "J"],
J: ["I"]
};
const DFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...graph[node], ...needVisit];
}
}
return visited;
};
console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]
구현 (Java)
import java.io.*;
import java.util.*;
/* 인접 리스트를 이용한 방향성 있는 그래프 클래스 */
class Graph {
private int V; // 노드의 개수
private LinkedList<Integer> adj[]; // 인접 리스트
/** 생성자 */
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i) // 인접 리스트 초기화
adj[i] = new LinkedList();
}
/** 노드를 연결 v->w */
void addEdge(int v, int w) { adj[v].add(w); }
/** DFS에 의해 사용되는 함수 */
void DFSUtil(int v, boolean visited[]) {
// 현재 노드를 방문한 것으로 표시하고 값을 출력
visited[v] = true;
System.out.print(v + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
// 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
if (!visited[n])
DFSUtil(n, visited); // 순환 호출
}
}
/** 주어진 노드를 시작 노드로 DFS 탐색 */
void DFS(int v) {
// 노드의 방문 여부 판단 (초깃값: false)
boolean visited[] = new boolean[V];
// v를 시작 노드로 DFSUtil 순환 호출
DFSUtil(v, visited);
}
/** DFS 탐색 */
void DFS() {
// 노드의 방문 여부 판단 (초깃값: false)
boolean visited[] = new boolean[V];
// 비연결형 그래프의 경우, 모든 정점을 하나씩 방문
for (int i=0; i<V; ++i) {
if (visited[i] == false)
DFSUtil(i, visited);
}
}
}
/** 사용 방법 */
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2); /* 주어진 노드를 시작 노드로 DFS 탐색 */
g.DFS(); /* 비연결형 그래프의 경우 */
}
인접 리스트로 구현(Java)
import java.util.*;
public class DFS_List {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
LinkedList<Integer>[] adjList = new LinkedList[n + 1];
for (int i = 0; i <= n; i++) {
adjList[i] = new LinkedList<Integer>();
}
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjList[v1].add(v2);
adjList[v2].add(v1);
}
for (int i = 1; i <= n; i++) { // 방문 순서를 위해 오름차순 정렬
Collections.sort(adjList[i]);
}
System.out.println("DFS - 인접리스트");
dfs_list(v, adjList, visited);
}
// DFS - 인접리스트 - 재귀로 구현
public static void dfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
visited[v] = true; // 정점 방문 표시
System.out.print(v + " "); // 정점 출력
Iterator<Integer> iter = adjList[v].listIterator(); // 정점 인접리스트 순회
while (iter.hasNext()) {
int w = iter.next();
if (!visited[w]) // 방문하지 않은 정점이라면
dfs_list(w, adjList, visited); // 다시 DFS
}
}
}
인접 행렬로 구현 (Java)
import java.util.*;
public class DFS_Array {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
int[][] adjArray = new int[n+1][n+1];
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for(int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjArray[v1][v2] = 1;
adjArray[v2][v1] = 1;
}
System.out.println("DFS - 인접행렬 / 재귀로 구현");
dfs_array_recursion(v, adjArray, visited);
Arrays.fill(visited, false); // 스택 DFS를 위해 visited 배열 초기화
System.out.println("\n\nDFS - 인접행렬 / 스택으로 구현");
dfs_array_stack(v, adjArray, visited, true);
}
//DFS - 인접행렬 / 재귀로 구현
public static void dfs_array_recursion(int v, int[][] adjArray, boolean[] visited) {
int l = adjArray.length-1;
visited[v] = true;
System.out.print(v + " ");
for(int i = 1; i <= l; i++) {
if(adjArray[v][i] == 1 && !visited[i]) {
dfs_array_recursion(i, adjArray, visited);
}
}
}
//DFS - 인접행렬 / 스택으로 구현
public static void dfs_array_stack(int v, int[][] adjArray, boolean[] visited, boolean flag) {
int l = adjArray.length-1;
Stack<Integer> stack = new Stack<Integer>();
stack.push(v);
visited[v] = true;
System.out.print(v + " ");
while(!stack.isEmpty()) {
int w = stack.peek();
flag = false;
for(int i = 1; i <= l; i++) {
if(adjArray[w][i] == 1 && !visited[i]) {
stack.push(i);
System.out.print(i + " ");
visited[i] = true;
flag = true;
break;
}
}
if(!flag) {
stack.pop();
}
}
}
}
Reference
반응형
LIST
'알고리즘' 카테고리의 다른 글
다익스트라 알고리즘 (0) | 2023.08.02 |
---|---|
[알고리즘] 다이나믹 프로그래밍 DP (0) | 2022.04.13 |
[알고리즘] BFS (0) | 2022.03.26 |
[알고리즘] 선택정렬 Selection Sort (0) | 2022.03.03 |