그래프 탐색 알고리즘

DFS와 BFS의 차이점과 개념 설명 그리고 관련 코드에 대해서 설명해드리겠습니다.

그래프 경로 탐색에 있어서는 DFS(깊이우선순회) , BFS(너비우선순회) 방식이 있습니다.

다음은 이진 트리의 탐색 구조입니다. 그래프도 크게 다른 건 없습니다. 

처음 시작 노드에서 12가 들어갈 곳을 탐색하기 위해 하나씩 내려가면서 

들어갈 위치가 아닌 노드 또는 말단 노드에 도달하면 다시 이 전 노드로 돌아가서 

검색하는 방법입니다.

그렇게 하여 들어갈 곳을 탐색하는 방식과 동일한 방식으로 

그래프 탐색도 진행됩니다. 

공통적으로 PreOrder기준으로 생각하자면 출발점을 기준으로 방문하지 않는 노드들을 접근하게 되고 마지막 노드까지 갔을 경우 
다시 돌아오면서(이 전 노드에서 다시 시작) 방문하지 않는 노드들을 방문하게 됩니다. 그리고 방문하였다고 체크하며 모든 노드들을 접근하는 방식입니다.  

(인접한 노드 중 방문하지 않는 노드에 접근합니다.)

이 과정을 반복하다가 시작노드에서도 더 이상 갈 곳이 없을 경우 종료하게 됩니다. 

(가장 마지막에 돌아가서 시작할 노드는 처음 스타트한 노드이기 때문 - root node)

 

DFS는 간선으로 연결된 노드들을 방문할 때 자식들을 우선적으로 탐색한다는 의미를 

가지고 있습니다.  노드 간 최단 거리의 길이가 커지는 쪽을 먼저 접근하여 탐색한다는 의미로 스택구조를 가지고 있습니다.

BFS는 DFS와 동일하지만 노드 간 최단 거리가 동일한 곳 부터 먼저 접근하는 방식입니다. 

즉, 형제노드를 먼저 접근하는 방식이지요. 따라서 수평 구조로 진행되기 때문에 

큐 구조를 가지고 있습니다.

(BFS,DFS) 그래프 탐색 알고리즘은 재귀함수로 진행되며, 함수 내에서 자기 자신을 다시 호출하는 구조로 생각해주시면 됩니다.

재귀함수에서 중요한 조건 중 하나는 종료조건을 잘 정리해야 한다는 것인데,

여기서는 방문한 노드일 경우가 종료조건이 될 것 입니다.

다음은 백준 2583번 문제입니다. 이 문제만 잘 해결하면 그래프 탐색 알고리즘 문제는 손 쉽게 해결하실 수 있습니다 .

< 이 문제는 dfs 또는 bfs 어떠한 것으로 풀던 무관합니다. >

[ dfs 핵심 코드 ] 

public static int dfs(int y, int x) {

if (visit[y][x] == true || square[y][x] == 1)

return 0;

int value = 1;

visit[y][x] = true;

if (x + 1 < n && square[y][x + 1] == 0)

value += dfs(y, x + 1);

if (x - 1 >= 0 && square[y][x - 1] == 0)

value += dfs(y, x - 1);

if (y + 1 < m && square[y + 1][x] == 0)

value += dfs(y + 1, x);

if (y - 1 >= 0 && square[y - 1][x] == 0)

value += dfs(y - 1, x);

return value;

}

종료 조건 

> 2차원 배열에서 해당 영역이 이미 방문한 경우 || 문제의 조건 중 1로 칠해진 부분은 방문하지 않는다.  

함수 내에서 이동 하는 조건을 설정해주고 그 안에서 다시 함수를 호출한다.

(value는 도형의 너비를 의미합니다.) 

관련 코드는 아래 링크에 있습니다. 참조해주세요 ^.^

https://github.com/Haamseongho/Algorithm_Study_For_Java/blob/master/Algorithm_Study_For_Java/Algorithm/%EC%B2%AB%20%EB%B2%88%EC%A7%B8%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EC%8A%A4%ED%84%B0%EB%94%94/src/makeNumberOne/%EC%98%81%EC%97%AD%EA%B5%AC%ED%95%98%EA%B8%B0.java