[백준]DFS와 BFS2

백준저지

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

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

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

전체 소스는

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

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

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

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

• BFS(Breath First Search)

- 너비 우선 탐색으로 시작 정점으로부터 가장 가까운 정점을 먼저 전부 방문을 하고 멀리 떨어져 있는 정점을 제일 나중에 방문하는 순회 방법이다.

- BFS를 코딩하는 방법으로 Queue를 이용한 방식이 있다.

• 방법

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

- 맨 왼쪽은 방문여부를 나타내는 배열, 아래쪽은 큐를 나타낸다.

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

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

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

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

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

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

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

- 그리고 다음 인접한 정점 3에 대해 방문 여부를 체크한다.

→ DFS와 BFS의 차이점이 여기서 갈린다. DFS의 경우 방금 방문한 정점(여기서는 2)에 대해 인접한 정점(2에 인접한 정점은 1이므로 1이 방문 여부를 확인)을 찾고, BFS의 경우 이전에 방문한 정점(여기서는 1)에 전부 방문할 때 까지 방문 여부를 확인한다.

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

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

- 그리고 다음 인접한 정점 4에 대해 방문 여부를 체크한다.

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

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

- 그리고 다음 인접한 정점이 없으므로!!!!

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

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

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

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

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

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

- 위 그림과 같이 4를 pop한다.

- 큐가 비어있으므로 함수를 리턴한다.

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

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

	for (int i = 0; i <= num; i++)
		visitArr[i] = false;

	queue.push(fir); 
	VisitVertex(visitArr, fir);
	while (!vecArr[visit].empty()) {
		for (int i = 0; i < (int)vecArr[visit].size(); i++) {
			int next = vecArr[visit][i];
			if (visitArr[next] == false) {
				queue.push(next);
				VisitVertex(visitArr, next);
			}
		}
		queue.pop();
		if (!queue.empty()) {
			visit = queue.front();
		} else {
			break;
		}
	}
}