[백준]DFS와 BFS1

백준저지

[DFS와 BFS]https://www.acmicpc.net/problem/1260

DFS와 BFS는 총 3번에 걸쳐서 포스팅을 하려고 한다.

이번 포스팅에서는 DFS에 대한 설명을 위주로 하려고 한다.

전체 소스는

http://vvshinevv.tistory.com/12 를 참고하자.

• 본문에 들어가기에 앞서 DFS와 BFS를 구현하기 위해서는 그래프 자료구조를 구현할 수 있어야 한다.

• 필자는 그래프 표현 방법 인접 행렬과 인접리스트 중 인접리스트를 이용하였다.

• 아래 예시는 백준저지에서 예시로 제공한 것을 사용한다.

• DFS(Depth First Search)

- 깊이 우선 탐색으로 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법이다.

- DFS를 코딩하는 방법으로는 재귀적인 방식과 Stack을 이용한 방식이 있다.(필자는 Stack을 이용하여 본 문제를 해결했다.)

• 방법

- 백준 예시를 기준, 1을 제일 먼저 방문한다고 가정한다.

- 맨 왼쪽은 방문여부를 나타내는 배열, 맨 오른쪽은 스택을 나타낸다.

- 회색은 이미 방문한 vertex, 분홍색은 방문 여부를 체크하는 중임을 나타낸다.

- 먼저 Main함수를 통해서 백준 예시를 입력하면 위 그림과 같이 2차원 배열이 생성된다.

※ vector STL에 대해 잘 모른다면, 일단 vec[0], vec[1]등 각 요소에 int형 배열을 담을 수 있다고만 생각하자.

※ Main함수는 전체 소스를 포스팅한 http://vvshinevv.tistory.com/12에 제시되어있다.

- DFS 함수를 호출하면 첫 번째 방문을 원하는 정점를 출력하고, 방문 여부를 True로 바꾸고 스택에 첫 방문 정점의 값(1)을 넣는다.

- 1과 인접한 정점 2에 대해서 방문 여부가 False이므로 방문을 시도한다.

- 정점 2를 방문하였으므로 2를 출력하고, 방문 여부를 True로 바꾸고 스택에 넣는다.

- 그리고 2와 인접한 1이 방문했는지를 체크한다.

→ DFS와 BFS의 차이점이 여기서 갈린다. 

→ DFS의 경우 방금 방문한 정점(여기서는 2)으로 이동 후 이동한 곳과 인접한 정점(2에 인접한 정점은 1이므로 1이 방문 여부를 확인, 방문 했으면 다음 인접한 정점 4의 방문여부를 확인)을 찾고,

→ BFS의 경우 이전에 방문한 정점(여기서는 1)에 전부 방문할 때 까지 방문 여부를 확인한다.(즉, 위 단계에서 첫 정점을 방문한뒤 그 정점을 기준으로 인접한 모든 정점들을 방문 1과 인접한 정점은 2, 3, 4가 있으며 2, 3, 4의 방문여부를 순차적으로 확인한 후 전부 방문이 되었다면 다음 정점으로 이동)

- 2와 인접한 정점 1은 이미 방문을 했으므로 다음 인접한 정점인 4를 방문했는지 체크한다.

- 2와 인접한 정점 4는 false이므로 방문을 시도한다. 

- 정점 4를 방문하였으므로 4를 출력하고, 방문 여부를 True로 바꾸고 스택에 넣는다.

- 그리고 4와 인접한 1이 방문했는지를 체크한다.

- 4와 인접한 1은 이미 방문을 했으므로 다음 인접한 정점인 2를 방문했는지 체크한다.

- 4와 인접한 2는 이미 방문을 했으므로 다음 인접한 정점인 3을 방문했는지 체크한다.

- 4와 인접한 정점 3은 false이므로 방문을 시도한다.

- 정점 3을 방문하였으므로 3을 출력하고, 방문 여부를 True로 바꾸고 스택에 넣는다.

- 그리고 3과 인접한 1이 방문했는지를 체크한다.

- 3과 인접한 1은 이미 방문을 했으므로 다음 인접한 정점인 4를 방문했는지 체크한다.

- 3과 인접한 4는 이미 방문을 했으므로 다음 인접한 정점이 없으므로!!

- 위 그림과 같이 3을 pop하고 다음 방문할 정점은 4가 된다!!!

- 4와 인접한 모든 정점을 확인하고 전부 방문을 했으므로!!!!

- 위 그림과 같이 4를 pop하고 다음 방문할 정점은 2가 된다!!!

- 2와 인접한 모든 정점을 확인하고 전부 방문 했으므로!!!!

- 위 그림과 같이 2를 pop하고 다음 방문할 정점은 1이 된다!!!

- 1과 인접한 모든 정점을 확인하고 전부 방문 했으므로!!!

- 위 그림과 같이 1을 pop한다.

- 스택이 비어있으므로 함수를 리턴한다.

아래는 위 내용을 구현한 함수이다.

/**
* @brief: 깊이 우선 탐색
* @param: vector<int> vecArr[], bool visitArr[], int num, int fir
*
* vecArr: 그래프 나타내는 배열(by 인접 리스트)
* visitArr: 카드 섞을 때 중복을 방지하는 기준 배열
* num: 정점의 개수
* fir: 처음 방문할 정점 변수
*/
void ShowDFS(vector<int> vecArr[], bool visitArr[], int num, int fir) {
	stack<int> stack;
	int visit = fir; // 방문 변수 선언

	for (int i = 0; i <= num; i++) // 방문 여부 전부 false
		visitArr[i] = false;

	stack.push(fir); 
	VisitVertex(visitArr, fir); 

	while (!stack.empty()) {

		bool visitFlag = false; // true: 인접한 정점에 방문, false: 인접한 정점을 모두 방문한 경우

		for (int i = 0; i < (int)vecArr[visit].size(); i++) {
			int next = vecArr[visit][i];
			if (visitArr[next] == false) {
				stack.push(next); 
				VisitVertex(visitArr, next);
				visit = next;
				visitFlag = true;
				break;
			}
		}

		if (visitFlag == false) { // 인접한 정점에 모두 방문을 했으니 가장 가까운 곳으로 가자!
			stack.pop();
			if (!stack.empty()) {
				visit = stack.top();
			}
		}
	}
}