[백준] 1260번 - 그래프, BFS, DFS

그래프는 정점과 간선으로 이루어진 자료구조이다. 트리는 그래프의 일종이다. 하지만 그래프는 정점간 간선이 없을 수도 있고 루트 노드, 부모 노드 개념도 존재하지 않는다. 

 

 

그래프는 인접 배열과 인접 리스트로 구현할 수 있다. 인접 배열은 2차원 배열에서 정점 i와 j가 이어져 있다면 ar[i][j]=1의 형식으로 1로 체크하고 이어져 있지 않다면 0으로 작성한다. 

 

 

인접 리스트는 연결되어 있는 정점의 정보만 저장한다. 인접리스트의 구현은 Vector 배열로 할 수 있다.

 

vector<int> jungjeom[MAX];
queue<int> Q;
bool visit[MAX];

 

jungjeom[i] 벡터는 정점 i 와 간선으로 이어진 정점들을 가지고 있다. BFS를 위해 큐를 생성하고 visit으로 정점을 방문했는지 안했는지 확인한다. 그리고 jungjeom[i] 벡터들은 BFS,DFS탐색을 위해 오름차순 정렬되어 있어야 한다.

 

void DFS(int x) {
	visit[x] = true;
	cout << x << ' ';
	for (int y : jungjeom[x]) {
		if (!visit[y])
			DFS(y);
	}
}

 

DFS(깊이 기반 탐색)는 시작 정점과 이어지는 가장 깊은 곳까지 탐색을 완료하고 다음 정점으로 넘어간다. 시작 정점에 대해서 visit배열에 체크하고 정점과 이어진 다른 모든 방문하지 않은 정점들에 대해 재귀 호출한다. 재귀 호출하기 때문에 정점과 이어진 가장 깊은 곳까지 탐색하고 정점과 이어진 두번째 가장 깊은 곳 순서로 탐색한다.

 

void BFS(int x) {
	Q.push(x);
	visit[x] = true;
	while (!Q.empty()) {
		int f = Q.front();
		Q.pop();
		cout << f << ' ';
		for (int y : jungjeom[f]) {
			if (!visit[y]) {
				Q.push(y);
				visit[y] = true;
			}
		}
	}
}

 

BFS(너비 기반 탐색)는 시작 정점으로부터 가까운 정점들은 먼저 방문한다. 먼저 큐를 생성해 큐에 시작 정점을 push하고 시작 정점과 이어진 다른 모든 방문하지 않은 정점들을 큐에 push한다. 그리고 큐에 push한 순서대로 같은 행동을 반복하기 때문에 먼저 큐에 push된 정점에 가까운 정점들이 먼저 출력된다.