DFS알고리즘

DFS 알고리즘이란?

깊이 우선 순회로 그래프에서 자식 노드를 다 찾아간 다음에 다음 인접 노드로 이동하는 알고리즘으로

횟수 N (노드)이 많을 경우 깊이 우선 탐색은 사용하기에는 많이 제약이 있을 것입니다.

깊이 우선 탐색에서는 인접행렬 또는 인접 리스트로 푸는 두 가지 방법이 있습니다.

공간복잡도를 줄이고자 저는 인접리스트로 풀겠습니다.

이 전에 BFS(너비우선순회)를 잠깐 다뤘었는데, 마찬가지로 DFS도 비슷하게 진행됩니다.

단, BFS와 다른 점은 Queue가 아닌 Stack을 사용해서 푼다는 점입니다.

이유는, BFS는 한 번에 여러 노드를 확인하면서 체크하지만, DFS는 자식노드를 

먼저 다 거친 다음에 이웃 노드를 체크하기 때문에 노드간의 순서가 중요합니다. 

따라서 쌓여서 순서가 정해져있는 스택을 사용하게 되는 것입니다.

인접 행렬로 푸는 방법은 이차원 배열을 사용해서 열에 대해서 모든 행을 다 돌고 

그 다음 열로 이동하게 됩니다. 

이 말인 즉, 한 노드에 대해서 딸려 있는 모든 자식 노드를 다 훑은 다음에, 

그 다음 노드로 이동한다는 뜻입니다.

인접 행렬을 이용해서 해도 좋지만, 배열 자체는 기본적으로 선언한 만큼의 공간을 쓰지 않는 경우가 많기 때문에, 무분별하게 공간이 남는 경우가 발생할 수도 있습니다.

따라서 앞서 말씀 드린대로, 인접리스트를 활용하여 풀겠습니다.

알고리즘 순서

1. ArrayList<ArrayList<Integer>> 를 선언한다. --> Integer 대신에 Node라는 클래스를 넣어서 

구조체 형식으로 풀어도 됩니다.

2. BFS에서 사용했던 방식 그대로 이용

[EX]

ㄱ. 큐가 비어 있지 않다면 반복문을 계속 돌린다.

ㄴ. 해당 노드를 방문했는지 여부를 boolean 함수나 배열로 체크한다.

ㄷ. 현재 노드에서 다음 노드로 이동할 때, 값을 증가시키며 체크한다. (dist)

DFS에서는 재귀함수로 호출하는데, ㄱ과 ㄴ 그리고 ㄷ 모두 사용됩니다.

아래 코드를 확인해보겠습니다.

---

private static void dfs(ArrayList<ArrayList<Integer>> ad , boolean[] visit , int node_here , boolean flag){

visit[node_here] = true; // 현재 노드는 방문하였다.

Stack<Integer> stack = new Stack<>();

stack.push(node_here); // 현재 노드 스택에 넣기

System.out.print(i + " " );

while(!stack.isEmpty()){

// 스택이 비어 있지 않을 경우 계속해서 체크 

int now = stack.peek(); // 스택에 가장 위에 있는 것이 현재 위치가 됩니다.

flag = false;

for(int i=1;i<=ad.size()-1;i++){

if((ad.get(now).get(i) == 1) && (!visit[i])){

// 한 노드에 대해서 리스트로 연결되어 있는데, 값을 가져올 때 노드가 연결된 것인지 체크한다.

// 연결된 다음엔 해당 노드(자식)를 방문하지 않았는지 체크한다.

stack.push(i); // 자식 노드를 스택에 넣는다.

System.out.print(i + " " ); 

visit[i] = true; // 자식 노드에 대해서 방문하였다고 체크해주기

flag = true;

break;

}

}

if(!flag)

stack.pop();

}

}

---

다음과 같이 dfs함수를 설정해주면 됩니다. 

여기서 중요한 것은 한 노드에 있어서 자식 노드가 연결될 때 ArrayList 구조로 연결 되어 있고

연결된 것을 확인한 다음, 해당 자식 노드를 방문하지 않았는지 체크 하고 나서 

dfs를 재귀로 다시 부르는 것입니다.

메인 함수는 다음과 같습니다.

---

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int N = scanner.nextInt();

visit = new boolean[N + 1];

stack = new Stack<>();

nodes = new ArrayList<>(N + 1); // 노드 만들기

for (int i = 0; i < N + 1; i++) {

nodes.add(new ArrayList<>());

// 각 인접 노드들을 리스트로 넣기 위해서 

// 모든 노드에 대해서 ArrayList를 안에다가 생성해줌

}

for (int i = 0; i < N; i++) {

int s1 = scanner.nextInt();

int s2 = scanner.nextInt();

nodes.get(s1).add(s2);

nodes.get(s2).add(s1);

// 각 노드 별로 연결 지어주고 서로서로

}

// flag = true;

dfs(nodes, visit, flag, 1);

}

---

처음 노드를 1로 잡고 진행한다고 가정하고 시작하기 때문에 마지막 파라미터 node(현재 위치)를 1로 둔 것입니다.

전체 코드는 다음과 같습니다.

---

package 탐색;

import java.util.ArrayList;

import java.util.Scanner;

import java.util.Stack;

public class DFS예제 {

private static boolean[] visit;

private static Scanner scanner;

private static boolean flag;

// 노드1은 6과 5에 연결

private static ArrayList<ArrayList<Integer>> nodes;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int N = scanner.nextInt();

visit = new boolean[N + 1];

stack = new Stack<>();

nodes = new ArrayList<>(N + 1); // 노드 만들기

for (int i = 0; i < N + 1; i++) {

nodes.add(new ArrayList<>());

// 각 인접 노드들을 리스트로 넣기 위해서 모든 노드에 대해서 ArrayList를 안에다가 생성해줌

}

for (int i = 0; i < N; i++) {

int s1 = scanner.nextInt();

int s2 = scanner.nextInt();

nodes.get(s1).add(s2);

nodes.get(s2).add(s1);

// 각 노드 별로 연결 지어주고 서로서로

}

// flag = true;

dfs(nodes, visit, flag, 1);

}

private static void dfs(ArrayList<ArrayList<Integer>> nodes2, boolean[] visit, boolean flag, int i) {

// 시작점 받고 시작

visit[i] = true;

Stack<Integer> stack = new Stack<>();

int n = nodes2.size() - 1;

stack.push(i);

System.out.print(i + " ");

while (!stack.isEmpty()) {

int v2 = stack.peek();

flag = false;

for (int j = 1; j <= n; j++) {

if ((nodes.get(v2).get(j) == 1) && (!visit[j])) {

stack.push(j);

System.out.print(j + " ");

visit[j] = true;

flag = true;

break;

}

}

if (!flag)

stack.pop();

}

}

}

---

감사합니다.