13강 - 너비 우선 탐색 (BFS)

1. 만들 것

1) 큐: 탐색 중인 노드들 저장 / q

2) bfs_visited: 방문 여부 표시

3) node: 현재 탐색할 노드 

4) 벡터(bfs_vector): 탐색을 마치고 탐색 순서 저장 (나중에 출력할 것)

 

2. 코드

1) 시작점 설정

1> 시작 노드를 큐에 삽입 / q.push(시작 노드)

2> 해당 노드를 방문했다고 표시 / bfs_visited[시작 노드] = true

2) 반복문

1> node에 큐의 맨 앞 요소를 저장 / int node = q.front()

2> node를 벡터에 삽입 / bfs_vector.push_back(node)

3> 벡터에 삽입하면 큐에서 node를 뺀다. / q.pop()

4> 반복문 (연결된 노드 탐색)

- 새로운 노드가 이 node와 연결된 것 && 방문하지 않은 것일 때 / if (arr[node][i] && !bfs_visited[i])

    - 새로운 노드를 큐에 추가한다. / q.push(i)

    - 방문하고 / bfs_visited[i] = true

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 1) 입력 받는 것 & 2) 설정
int arr[1005][1005]; // 연결 여부 저장할 array
bool bfs_visit[1005]; // 방문 여부 저장할 array
int n, m, v; // 입력 변수 선언

int main() {
	cin >> n >> m >> v; // 입력 변수 받기 (정점, 간선, 시작점)

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		arr[u][v] = arr[u][v] = 1;
	} // 입력 변수 받기 (연결 여부)

	vector<int> bfs; // 탐색 순서 저장 (나중에 출력할 것)
	queue<int> q; // 탐색 중인 노드 저장 (큐로 저장)

    // 3) 시작점
	q.push(v);
	bfs_visit[v] = true;
    // 4) queue가 완전히 빌 때까지 반복
    while (!q.empty()) {
		int node = q.front(); // 큐에 저장된 내가 이미 탐색한 노드를 저장
		bfs.push_back(node); // 이 노드를 vector에 저장

		q.pop(); // 큐에서 제외
		for (int i = 1; i <= n; i++) {
			if (arr[node][i] && !bfs_visit[i]) { // 이 노드 주변부 중에서 방문 안 한 곳이 있으면
				bfs_visit[i] = true; // 그 노드를 방문 했다고 표시하고 
				q.push(i); // 큐에 추가한다.
			}
		}
	}

	for (int i = 0; i < bfs.size(); i++) {
		cout << bfs[i] << ' ';
	}
}