728x90
DFS (Depth Firsh Search)
- 그래프 탐색의 한 종류
- 깊이 우선 탐색이라고 부름
- 루트 노드나 random 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후 돌아와 다른 노드로 탐색하는 방식
- stack을 사용
장점
1) 한 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적음
2) 목표 노드가 깊은 단계에 있을 경우 답을 빨리 구할 수 있음
단점
1) 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있음
2) 얻어진 해가 최단 경로가 된다는 보장이 없음.
숫자가 낮은 점부터 탐색을 하는것이 국룰이라고 생각하면 됩니다.
시작정점 : 1번일 경우
1 - 2 - 4 - 8 - 5 - (8) - 6 - 3 - 7 (8번을 2번 택했는데, 두번째 8은 두번 탐색하는게 아니고 거쳐가는 곳)
DFS 구현방법 -1
인접 행렬 (Adjacency Matrix)
-> 인접행렬은 행렬로 정점들 사이의 관계를 표현하는 것
간선 방향의 존재 유무에 따라 표현하는 방법에 차이가 있음.
1번 노드는 2,3번과 연결 | 2번 노드는 1,4번과 연결 | 3번 노드는 1,3번과 연결 | 4번 노드는 2,3번과 연결.
package 자료구조;
import java.util.Scanner;
public class dfs {
//변수 선언
static int edge; //간선의 수
static int vertex; // 정점의 수
static int[][] map; //정점 간의 연결의 정보를 담는 객체
static boolean[] visit; //정점을 방문했는지 체크하기 위한 객체
public static void main(String[] args) {
//스캐너 입력
Scanner sc = new Scanner(System.in);
vertex = sc.nextInt();
edge = sc.nextInt();
map = new int[vertex+1][vertex+1];
visit = new boolean[vertex+1];
//조건
for (int i = 0; i < edge; i++) {
int start = sc.nextInt();
int next = sc.nextInt();
map[start][next] = 1;
map[next][start] = 1;
}
dfs(1);
}
public static void dfs(int start) {
visit[start] = true;
System.out.println(start + " ");
//시작점에서 정점까지 수 만큼 반복하면서 연결되있는지 보고, 방문했는지 체크
for (int i = 1; i < vertex+1; i++) {
if(map[start][i] == 1 && visit[i] ==false) {
dfs(i); //재귀호출 (이거는 잘 몰라서 따로 공부해야함)
}
}
}
}
import java.util.Scanner;
public class dfs {
//변수 선언
static int edge; //간선의 수
static int vertex; // 정점의 수
static int[][] map; //정점 간의 연결의 정보를 담는 객체
static boolean[] visit; //정점을 방문했는지 체크하기 위한 객체
public static void main(String[] args) {
//스캐너 입력
Scanner sc = new Scanner(System.in);
vertex = sc.nextInt();
edge = sc.nextInt();
map = new int[vertex+1][vertex+1];
visit = new boolean[vertex+1];
//조건
for (int i = 0; i < edge; i++) {
int start = sc.nextInt();
int next = sc.nextInt();
map[start][next] = 1;
map[next][start] = 1;
}
dfs(1);
}
public static void dfs(int start) {
visit[start] = true;
System.out.println(start + " ");
//시작점에서 정점까지 수 만큼 반복하면서 연결되있는지 보고, 방문했는지 체크
for (int i = 1; i < vertex+1; i++) {
if(map[start][i] == 1 && visit[i] ==false) {
dfs(i); //재귀호출 (이거는 잘 몰라서 따로 공부해야함)
}
}
}
}
참고 : https://www.youtube.com/watch?v=waPwUJu0-lo&list=PLlTylS8uB2fCoXCVtfJ0wzotOU8a3ti6M
728x90