(백준/c++) 24444~24445 너비 우선 탐색 1~2

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

인접리스트, BFS

주의

1. 시간 초과 나왔던 부분:
- 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다. 
- C++ 개행 부분을 std::endl을 사용하면 시간초과가 뜬다..ㄷㄷ "\n"으로 사용해야 한다.

2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다. 

3. 24445 번은 내림차순으로 정렬해줘야 한다. sort는 less<>가 default이기 때문에 greater<>를 사용해주거나 함수를 만들어서 적용해준다. 

---

24445번 sort 부분만 다르기 때문에 24445번 첨부 합니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <deque>
	using namespace std;
	#define MAXR 100'001
	void BFS(int start);
	vector<int> Edge[MAXR];
	vector<pair<bool, int>> visite( MAXR, make_pair(false, 0));
	int gOrderOfVisit;
	int main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, M, R;
	cin >> N >> M >> R;
	for (int i = 1; i <= M; ++i) {
	int u, v;
	cin >> u >> v;
	Edge[u].push_back(v);
	Edge[v].push_back(u);
	}
	for (int i = 1; i <= N; ++i)
	{
	if (!Edge[i].empty())
	sort(Edge[i].begin(), Edge[i].end(), greater<>()); // - 24445번
	// sort(Edge[i].begin(), Edge[i].end()); // - 24444번
	}
	BFS(R);
	for (int i = 1; i <= N; ++i)
	cout << visite[i].second << "\n"; // endl -> "\n" 안하면 시간초과 ㄷㄷㄷ..
	}
	void BFS(int start)
	{
	deque<int> que;
	que.emplace_back(start);
	visite[start].first = true;
	while (!que.empty())
	{
	int _next = que.front();
	que.pop_front();
	visite[_next].second = ++gOrderOfVisit;
	for(auto & e : Edge[_next]) {
	if (!visite[e].first) {
	visite[e].first = true;
	que.emplace_back(e);
	}
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub