바이러스
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
int dfs(int n, vector<vector<int>> &adj_list){
int count = 0;
stack<int> s;
vector<bool> visited(n+1, false);
s.push(1);
visited[1] = true;
while (!s.empty()){
int curr = s.top();
s.pop();
for (auto next: adj_list[curr]) {
if (visited[next]) {
continue;
}
visited[next] = true;
s.push(next);
count++;
}
}
return count;
}
int bfs(int n, vector<vector<int>> &adj_list){
int count = 0;
queue<int> q;
vector<bool> visited(n+1, false);
q.push(1);
visited[1] = true;
while (!q.empty()){
int curr = q.front();
q.pop();
for (auto next: adj_list[curr]) {
if (visited[next]) {
continue;
}
visited[next] = true;
q.push(next);
count++;
}
}
return count;
}
int main() {
int n, m, a, b;
cin >> n >> m;
vector<vector<int>> adj_list(n+1, vector<int>());
for(int i=0; i<m; i++) {
cin >> a >> b;
adj_list[a].push_back(b);
adj_list[b].push_back(a);
}
cout << dfs(n, adj_list);
}
- 한 컴퓨터가 걸리면 연결돼있는 모든 컴퓨터가 걸린다는점에서 그래프 탐색을 해야함
- 그러므로 그 방법으로 dfs나 bfs가 있는건데, 공부를 위해서 두가지 방법 모두 짜봄
- 방식은 항상 똑같음
- queue나 stack이 빌때까지 while문을 돌면서
- pop을 해서 값을 빼고,
- 연결된 노드들을 하나하나 다 돌면서 방문한 곳이 아니면 push하기
국영수
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct student {
string name;
int kor, eng, math;
};
bool compare(const student &a, const student &b) {
if (a.kor != b.kor) {
return a.kor > b.kor;
}
if (a.eng != b.eng) {
return a.eng < b.eng;
}
if (a.math != b.math) {
return a.math > b.math;
}
return a.name < b.name;
}
int main() {
int n;
cin >> n;
vector<student> school(n);
for (int i = 0; i < n; i++) {
cin >> aschool[i].name >> school[i].kor >> school[i].eng >> school[i].math;
}
sort(school.begin(), school.end(), compare);
for (int i = 0; i < n; i++) {
cout << school[i].name << '\n';
}
return 0;
}
- 정렬문제로, 되게 쉬운편
- 그냥 sort를 쓰면되는데, 숫자가 아니다 보니까 compare함수를 만들어야함
- 또한 들어오는값이 여러개니까 객체를 만들어서 사용해야함
- 그거외에는 그냥 간단!
중복제거 정렬
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, input;
set<int> s;
cin >> n;
while (n--) {
cin >> input;
s.insert(input);
}
for (auto iter = s.begin(); iter != s.end(); iter++) {
cout << *iter <<' ';
}
return 0;
}
- 이번주 시간이 빠듯해서 좀 쉬운걸 풀었다 ^^..
- 중복을 없애고 정렬을 하려면 그냥 set을 사용하면 된다.
- set은 랜덤접근이 안되니까 iter쓰는거만 안까먹으면 끝!