[자료구조] DFS (깊이우선탐색)

 

23.09.14

이제와서 보니 뭘 이렇게 열심히 했나 싶기도 하다.

어차피 문제풀때는 stack과 재귀(보통 재귀가 90%)만 쓰는데 이걸 왜 구현하려고 했는지...

DFS 아는 사람들은 이거 스킵해도 됩니다. 머리만 복잡해져요...

 

---

[ DFS 구현시 STACK을 사용하는 이유 ]

DFS 알고리즘은 재귀다

 

재귀임을 이해하면 된다.
( 하지만 책은 재귀로 구현하지 않고 그냥 while문으로 구현했다.
일단 while문으로 구현한 것으로 원리를 파악하고 추후에 재귀로 구현해보겠다 )

 

참고로 보통은 matrix를 이용하여 재귀로 구현하는게 일반적이고 쉽다

코테때는 matrix나 python의 딕셔너리를 이용하면 된다.

하지만 이 책에서는 DFS의 원리를 이해시키는 것이 목적이기에

DLinkedList를 이용하여 DFS를 구현했다.

 

DFS 설명을 보면
스택(경로추적을 위한) 과 배열(방문정보를 담을)이 필요하다는 것을 먼저 설명하고
이 두 가지를 매우 강조하는데

이보다 먼저 알아야하는 것이 재귀적인 구조라는 것이다.

재귀적인 구조이기에 STACK이 필요한 것이다!!

 

왜냐하면 재귀와 STACK은 매우 비슷한 성격을 가지고 있기 때문이다.

 

재귀도 함수의 호출관계를 보면 FILO(First In Last Out) 구조이다.

재귀#1 -> 재귀#2 -> 재귀#3 -> 재귀#4 -> .... -> 재귀#N

으로 호출되서 #N에서 끝났다고 하면

return될때

재귀#N return -> 재귀#N-1 return -> 재귀#N-2 return -> ... -> 재귀#2 -> 재귀#1

이렇게 마지막꺼 부터 첫번째 방향으로(아래에서 위로) return 과정이 진행되기 때문이다!

 

따라서 STACK을 사용하여 DFS를 구현하는 것이다!

 

이 선행관계를 인지하고 있어야한다.

 

아래 예시를 보면서 DFS알고리즘을 설명하겠다.

 

---

[ DFS의 원리 ]

일단 룰은 이 두가지 밖에 없다.

1. 방문했으면 스킵

-> 방문의 유무를 알기 위해 배열을 사용

2. 방문할게 없으면 자기를 부른 놈을 호출

-> 부른 놈을 호출하기 위해 스택을 사용

DFS를 그림으로 표현하면 다음과 같다.

 

 

 

---

[ VisitVertex ]

 

DFS를 구현하기 전에 필요한 보조함수이다.

 

이 함수에는 두 가지 기능이 있다.

 

1) 방문여부 전달

2) visitInfo[visitV] = 1 로 최신화

이 VisitVertex함수는 방문정보배열인 visitInfo배열을 관리하는 함수로
첫 방문이면 1로 바꿔주고 return 1을 해주고 아니면 return 0을 한다.

따라서 우리가 직접 visitInfo 배열을 손대지 않고 이 함수를 이용해서

visitInfo배열을 참조하려는 쪽으로 노력해야한다.

이 함수를 이용해서 방문여부를 확인하고 이를 통해 해당 노드 참조를 제한할 수 있다!

 

코드를 작성해보면 이 함수의 위치가 매우 중요하다. 

어디 사이에 들어가느냐가 중요하다. 

int VisitVertex(ALGraph* pg, int visitV) {
	// 첫 방문이면
	if (pg->visitInfo[visitV] == 0) { 
		pg->visitInfo[visitV] = 1;
		printf("%c", visitV + 65);
		return 1; 
	}
	// 방문한 적 있으면
	else return 0;
}

 

---

[ DFS ]

 

위 두 그림을 구현한 코드는 아래와 같다.

 

void DFSShowGraphVertex(ALGraph* pg, int startV) {
	Stack stack;
	int visitV = startV;
	int nextV;

	StackInit(&stack);
	VisitVertex(pg, visitV); //시작점 방문배열에 저장 + 출력
	SPush(&stack, visitV); // stack에 시작점 저장

	// visitV와 연결된 노드가 있으면
	while(LFirst(&(pg->adjList[visitV]), &nextV)) { // nextV에 저장
		
		int visitFlag = 0;

		// nextV가 첫 방문이면
		if (VisitVertex(pg, nextV)) {
			SPush(pg, nextV); // stack에 nextV 저장
			visitV = nextV; // visitV 최신화
			visitFlag = 1;
		}

		// nextV를 방문한 적이 있으면
		else {
			// nextV가 방문한 놈이 아닐때까지 계속 while문을 돈다
			while (LNext(&(pg->adjList[visitV]), &nextV)) {

				// 첫 방문이면
				if (VisitVertex(pg, nextV)) {
					SPush(pg, nextV); //stack에 nextV 저장
					visitV = nextV; // visitV 최신화
					visitFlag = 1;
					// 해당 nextV의 adjList를 참조하기 위해 break를 한다!
					break;
				}
			}
		}

		// cf) 이 과정에서 해당 리스트가 모두 돈 노드들로 구성되어 있으면 SPush가 전혀 되지 않는다!

		// nextV가 첫방문일때랑 아닐때 모두 visitFlag = 1로 초기화가 됨
		// 그럼 visitFlag 가 0일때는 무엇을 의미? 
		// 다음 정점이 없거나(이제 끝이거나) or 아예 정점이 없는 노드이거나
		// 연결된 노드들이 모두 방문했던 노드일때!
		// visitFlag가 0일때는 
		if(visitFlag==0){
			if (SIsEmpty(&stack)) {
				break;
			}
			else {
				visitV = SPop(&stack);
			}
		}
	}

	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

DFS 함수는
SPush 즉 스택이 활용되는 시점과 visitFlag가 1일때와 0일때 가 가장 중요한 상황이다.

 

다음은 어떤 노드가 첫 방문이면 무조건 진행되는 코드들이다.

 

어떤 노드가 첫 방문이면
SPush로 스택에 해당 노드가 들어가고
무조건 visitV = nextV이고 0으로 초기화됬던 visitFlag = 1이 된다
따라서 다시 while문으로 돌아가서
새로운 리스트(visitV가 최신화 되었으므로)에 대한 LFirst를 진행하게 된다

하지만 해당 노드가 방문 해본 노드이거나 

해당 리스트에서 모든 노드가 방문을 한 노드이면 ( 모든 노드의 visitInfo==1 이면 )
visitFlag 는 계속 0으로 남아있는다.

따라서 마지막 if(visitFlag==0) 을 호출하게 된다

 

---

[ visitFlag==0 일때의 상황 ]

 

두번째 그림을 예시로 들어보겠다.

예를 들어 이 상황에서 E까지 다 참조를 했고
"E에서 D를 넘어 F로 가는 상황" 을 보자

이때 F는 E랑만 연결되어 있는데
E는 한번 방문했던 노드로 visitInfo[E] (방문정보배열)가 1로 되어 있다.

그러면 else의 while문을 돌게 되는데
이때 연결된 노드가 E밖에 없고 E는 한번 방문했던 노드이니
if ( VisitVertex ) 가 FALSE이다.

그러므로 visitFlag = 0이 유지되고
맨 마지막의 if ( visitFlag == 0 ) 을 작동시킨다.

만약 SIsEmpty이면 연결된 모든 정점을 출력한 경우이므로

break하여 전체함수를 종료시키지만,

스택에 아직 정점이 남아있다면 Spop을 통해
방문경로를 순차적으로 하나씩 뽑는 과정을 거친다.

따라서 F를 탐색할때

Spop을 통해 F가 나오고
또 다시 F탐색하고

이때 다 방문했으니 visitFlag==0 으로 유지되므로
또 Spop을 통해 E가 나오고
또 다시 E를 처음부터 탐색하고 ( visitV = SPop(&stack) 이고 큰 while문이 LFirst함수로 시작하므로 )

F의 visitInfo==1 이므로 F는 방문노드이니 넘기고
F 다음의 G를 마주하게 된다.

G의 리스트에도 E밖에 없으니 위 E와 동일한 과정을 거친다.

 

이렇게 끝까지 다 탐색이 되었으면 이제 SPop(&stack)을 통해 

다시 위로 올라가는 과정을 거친다.

맨 첫번째의 빨간색 화살표가 그 과정이다.