14-2
그래프의 탐색
오늘은 저번 시간에 배운 "그래프"를 써먹어서, 탐색할 수 있는 자료구조를 만들거다. 꽤 어려울 수도 있으니, 꼼꼼히 복습하도록 한다.
이번 탐색 시간엔, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두가지를 다룰 것이다. 각각 내용이 꽤나 많으므로, 집중하자.
깊이 우선 탐색 (Depth First Search)
우선, 깊이 우선 탐색 방법이다. 이 책에서 설명하는 예시대로 이해하는게 "정의"를 명확하게 알기보단 "이해"를 하는데 많은 도움이 되는 것 같아서, 이 예시를 따라쓰겠다.
만약 아래와 같은 예시가 있다고 치자.
초등학생때나 중학생때 흔히 볼 수 있었던 "비상연락망"을 그래프로 표현한 것이다.
동이란 친구부터 시작한다. 여기서, 모든 사람이 "한 사람에게만 연락한다"는 생각을 가지고 있다고 치자. 그러면 임의로 각자 연결되어있는 사람 중 한명씩 연락을 돌린다면, 아래와 같은 순서로 연락이 차례차례 간다.
이렇게. 동->지민->민->정->수. 총 다섯명이 연락을 받게된다.
하지만, 아직 지율이는 연락을 받지 않았다.
왜 순서가 저래요?
물론, 민이 정 / 수 / 지율중 하나에게 연락을 돌릴 수 있지만, 난 임의로 저렇게 했다.
그런데, 저기서 "수"의 상황을 보면, 자기가 연락해야할 사람들에게는 이미 연락이 다 돌아가있는 상태다. 이 상황에서 "수"는 자기에게 연락을 줬던 "정"에게 아래와 같이 얘기한다.
"야, 나랑 연결된 애들은 다 연락 받았어. 니랑 연결된 애들중에 연락 못 받은애 있으면 그리로 연락해!"
그런데, 정도 똑같은 상황이라, 민에게 다시 위와 똑같은 얘기를 하며 연락을 한다.
민이 연락을 받았다.
어? 근데, 지율이는 아직 연락을 안받았네? 그래서, 민은 지율이에게 연락을 한다.
이제, 모든 사람이 연락을 다 받았다. 끝!
,,을 내면 안된다!!
만약 동의 왼쪽에 새로운 친구가 하나 연결이 되었다치면, 그 친구는 연락을 못받게된다! 그래서, 이 깊이 탐색 트리는 마지막에 다시 처음 시작점으로 돌아가야 한다.
이렇게, DFS의 과정이 끝이 나게 된다.
이 DFS에서 사람 = 정점 / 연락 = 간선이라고 가정하면, 세개의 핵심 포인트가 있다.
1. 한 사람에게만 연락을 한다.
2. 연락할 사람이 없다면, 자신에게 연락한 사람에게 다시 알린다.
3. 처음 연락을 시작한 사람의 위치에서 연락이 끝난다. (탐색이 끝난다)
너비 우선 탐색(Breadth First Search)
앞서 본 DFS는 "한 사람에게만 연락을 취하는 방식" 이였다. BFS는 이와 달리 "자신에게 연결된 모든 사람에게 연락을 취하는 방식"이다.
앞서 본 그림과 똑같은 그림으로 설명을 하겠다.
이번엔 시작점을 바꿨다. BFS 방식은 동부터 시작하면, 너무 설명할게 없어진다.
여기서, B(Breadth)는 "폭", "넓이"를 의미하는데, 이를 윗 그림에 적용시키면 한 사람을 기준으로 메세지를 전달하는 사람의 수(폭)와 같다. 만약 지율이를 기준으로 하면, 동 / 민 두명에게 연락이 가능하니 Breadth = 2라고 볼수있다.
여기서 우리는 서로 텔레파시로(?) 누가 연락을 받았는지, 안받았는지 알고있다고 가정한다. 태클은 안받는다. 현실의 연락을 생각하지말고, 가상의 예시라고 생각하자..
여튼, 지민이는 자기가 연락이 가능한 동/민에게 모두 연락을 돌린다.
여기서 동 / 민도 자신에게 연결된 사람들에게 연락을 해야한다. 그런데 여기서 "누가 먼저 연락을 취한다"는 신경쓰지 말자. 그냥 임의로 위의 예시에서 "동"이 "민"보다 연락을 빨리 전달했다고 가정한다.
이제, 민의 차례.
이렇게된다. 여기서 완전 "끝"이냐? 아니다, "정"과 "수"에게도 기회가 돌아가고, 만약 이 두사람이 더 연결된 사람이 없다고 확인되면 "끝"이다! 만약 수나 정에게 연락을 해야할 사람이 더 있었다면, 저기서 끝내면 안되니까.
이렇게, DFS, BFS에 대한 기본 개념은 끝이다.
"구현"
구현에 들어가기 전, 과정 이해
DFS, BFS 다 다루긴 할건데, 각각 구현에서 다뤄야할 내용이 너무 많아서 Ch.14-3에 BFS를 따로 설명하겠다.
이번에는, DFS만 다루겠다.
우선, 위의 DFS의 그림을 보고 설명하겠다.
우리는 DFS의 과정을 구현하기 위해선, 두가지가 필요하다.
- 스택 for 경로 정보의 추적
- 배열 for 방문 정보의 기록
이렇게.
자, 첫 과정부터 보자.
자, "동"에게 방문했다. 그러면 방문기록 체크.
이제, 지민에게로 간다.
이렇게, 다음사람에게 가면, 방문 기록을 체크해주며 그 앞사람을 STACK에 push 해준다.
이렇게, 수까지 쭉 가보자.
이렇게, 수까지 가며 그 앞의 경로 추적 결과인 "동, 지민, 민, 정"이 stack으로 옮겨갔다.
그럼, 여기서 다시 정을 거쳐 민으로 가야한다. 그러면 방문 기록은 그대로 놔두면 되는데, 경로 추적 결과는 어떻게 해야할까?
이렇게, 다시 "정"과 "민"을 POP해버리면 된다.
그 다음, 지율이에게로 간다.
그러면 뭐, 다시 민을 push해주면 된다.
그러면 이제 다시 동에게로 가서 탐색을 끝낼 준비를 해야한다. 어떻게 해야할까? 이 과정의 앞부분들을 잘 살폈다면 대충 때려맞출 수 있을 것이다.
.
.
.
.
.
.
바로 답을보지말고, 생각해보자!
.
,
.
.
.
.
이제 알려주겠다.
이렇게, 다시 돌아오면서 하나 하나씩 POP을 해주면 된다.
만약 앞의 과정(+그림)을 다 이해했다면, DFS 구현을 위한 기본적인 과정은 다 이해했다! 이제 실제 구현으로 가보자.
진짜 구현
우리는 14-1에서 그래프의 헤더파일과 소스파일을 구현했었다.
이 헤더파일과 소스파일에 각각 DFS 와 관련된 함수의 선언 / 정의를 추가해서, 그래프+DFS 가 같이 들어간 헤더파일과 소스파일을 다시 구현할 것이다.
void DFShowGraphVertex(ALGraph *pg, int startV);
// DFS를 기반으로 그래프의 정점 정보를 출력한다.이 함수가 들어갈 것이다.
그리고, 앞서 스택을 썼으므로 Stack과 관련된 헤더파일, 소스파일이 포함되어야 할 것이고, 그래프를 구현하는데 LinkedList를 썼으므로 이와 관련된 헤더파일, 소스파일이 포함되어야 할것이다.
파일의 자세한 목록은 깃허브를 참고하자.
일단, DFShowGraphVertex의 함수 선언이 추가된 헤더파일을 보이겠다.
#ifndef __AL_GRAPH_DPS__
#define __AL_GRAPH_DPS__
#include "DLinkedList.h" // 연결 리스트 가져다 씀
enum {A, B, C, D, E, F, G, H, I, J}; // 정점 상수화
typedef struct _ual {
int numV;
int numE;
List *adjList;
int *visitInfo; // New. 방문 이력 남기기. 탐색이 진행된 정점의 정보를 담는다.
} ALGraph;
void GraphInit(ALGraph *pg, int nv);
void GraphDestroy(ALGraph *pg);
void AddEdge(ALGraph *ph, int fromV, int toV);
void ShowGraphEdgeInfo(ALGraph *pg);
void DFShowGraphVertex(ALGraph *pg, int startV);
// New. 정점의 정보를 DFS 기반으로 출력한다.
#endif구조체에 int *visitInfo; 라는 멤버가 추가되었고, 새로운 함수의 선언이 추가되었다.
이 visitInfo로 인해, GraphInit과 GraphDestroy에는 새로운 문장이 추가될것이다.
이 "추가된 내용"을 보도록 하자.
void GraphInit(ALGraph *pg, int nv) {
. . . .
pg->visitInfo = (int *)malloc(sizeof(int)*pg->numV);
// 정점의 수를 길이로 하여 배열을 할당한다.
// 각 정점마다의 방문 정보를 남겨야 하니깐.
memset(pg->visitInfo, 0, sizeof(int)* pg->numV);
// visitInfo 초기화
}
void GraphDestroy(ALGraph *pg) {
. . . .
if(pg->visitInfo != NULL) {
free(pg->visitInfo); // 방문정보가 남아있다면, 초기화
}
}각 함수의 앞부분은 똑같고, 위에 추가된 내용들만 새로이 등장한 친구들이다.
그리고, 이번엔 DFS 기반 구현의 핵심이 될 수 있는 두 함수를 보자.
void DFShowGraphVertex(ALGraph *pg, int startV);
int VisitVertex(ALGraph *pg, int visitV);
// 정점의 방문 진행?? VisitVertex는 헤더파일에 없었잖아요
이 함수는 정점의 방문을 목적으로 하는데, 소스파일에 정의가 될 것이다. DFShowGraphVertex 함수 내에서 호출이 이루어질것이다.
int VisitVertex(ALGraph *pg, int visitV) {
// 0은 "방문 안함", 1은 "방문 함"으로 가정
if(pg->visitInfo[visitV] == 0) {
pg->visitInfo[visitV] = 1;
printf("%c ", visitV + 65);
return TRUE; // 방문 성공
}
return FALSE; // 방문 실패
}이번엔 DFShowGraphVertex를 보일텐데,, 정말 어마무시하게 길다.
놀라지 말자.
void DFShowGraphVertex(ALGraph *pg, int startV) {
// 그래프의 정점 정보를 출력한다. (DFS 기반)
Stack stack;
int visitV = startV; // 시작점부터 돌아야하니깐!
int nextV;
StackInit(&stack);
VisitVertex(pg, visitV); // 시작 정점을 방문
SPush(&stack, visitV); // 시작 정점의 정보를 Stack으로 이동.
// 아래 while문에서 모든 정점의 방문이 이뤄진다.
while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {
// visitV에 담긴 정점과 연결된 정점의 방문을 시도한다.
// visitV와 연결된 정점의 정보가 nextV에 담긴 상태에서 이하를 진행.
// 위의 LFirst 함수 호출 -> visitV에 연결된 정점 하나 get -> 이 정점의 정보를 nextV에 저장
int visitFlag = FALSE;
// nextV에 담긴 정점의 정보로 방문 시도!
if (VisitVertex(pg, nextV) == TRUE) { // 방문에 성공했을 시.
SPush(&stack, visitV);
visitV = nextV;
visitFlag = TRUE; // while문 재시작. 다른 정점의 방문을 시도한다
}
else
{ // 만약 방문을 실패했다면, 다른 정점을 찾는다.
while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
if(VisitVertex(pg, nextV) == TRUE) {
SPush(&stack, visitV);
visitV = nextV;
visitFlag = TRUE;
break;
}
}
}
if (visitFlag == FALSE) { // 만약, 추가로 방문한 정점이 없다? (정점 방문 실패)
// 스택이 비면 탐색의 시작점으로 되돌아온거다.
if(SIsEmpty(&stack) == TRUE) { // 시작점으로 되돌아왔다. (= 스택에 든게 없다)
break;
} else { // 시작점으로 돌아온게 아니라면
visitV = SPop(&stack); // 되돌아가
}
}
}
memset(pg->visitInfo, 0, sizeof(int) * pg->numV); // 이후의 탐색을 위해, 탐색 정보를 초기화한다.
}주석을 잘 읽어보며 이해하자..
main함수는 위에서 언급한 github을 참고.
여기까지.
