[S2] 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1 C++ 너비 우선 탐색

리뷰

 

https://www.acmicpc.net/problem/24444

양방향 간선...!!!!!!!

 

 

전역 변수

• N : 배열의 최대 크기를 저장할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• r : 시작 노드를 저장할 변수
• it : 정점에 도착한 시간을 기록할 배열
• v : 방문 체크를 진행할 배열
• lst : 인접 리스트를 저장할 트리 집합 배열

 

함수

1. bfs

void bfs()

 

너비 우선 탐색을 통해 각 정점에 도착한 시간을 기록하는 함수

1. 정수형 큐 q를 초기화 하고, 시작 노드 r을 push해준다.
2. 시간을 기록할 변수 t를 1로 초기화 하고, it배열의 r인덱스에 t를 저장 후 후위 증가시켜 준다.
3. v배열을 통해 r번 노드에 방문처리를 진행해 준다.
4. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 빼내어 변수 cur에 저장해준다.
5. cur의 인접 리스트를 순회하며 방문처리 되어 있으면 continue를 진행해 준다.
6. 방문처리 되어 있지 않으면 방문 처리 후 it배열에 t를 저장후 후위 증가시켜 준다, 이후 q에 해당 노드를 push해준다.

 

문제풀이

1. n, m, r 값을 입력 받고, m개의 간선 정보를 입력 받아 양방향으로 추가해 준다.
2. bfs함수를 호출하여 it배열의 값을 초기화 해준다.
3. 1 ~ n번 노드를 순회하며 it배열에 저장된 값을 줄 바꿈을 기준으로 출력해 준다.

 

트러블 슈팅

1. 무방향 그래프라고 해서 무의식 적으로 단방향 간선을 추가해 주었다.
2. 양방향 간선으로 변경 후 제출하니 AC를 받았다.

 

참고 사항

• set을 사용해서 그런가 메모리가 꽤나 많이 소요되었다.
• 인접 리스트를 vector 자료구조를 사용하고 모든 간선을 입력 받고, 정렬 시 메모리 사용량이 좀 줄을 것 같다.

 

정답 코드

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

const int N = 100001;
int n, m, r;
int it[N];
bool v[N];
set<int> lst[N];

void bfs() {
	queue<int> q;
	q.push(r);
	int t = 1;
	it[r] = t++;
	v[r] = true;

	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int i : lst[cur]) {
			if (v[i]) continue;
			v[i] = true;
			it[i] = t++;
			q.push(i);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> r;
	while (m--) {
		int a, b; cin >> a >> b;
		lst[a].insert(b);
		lst[b].insert(a);
	}
	bfs();
	for (int i = 1; i <= n; ++i) cout << it[i] << "\n";
}