[BOJ] 바이러스, 국영수, 중복제거 정렬

마코레·2022년 7월 17일
0

코테공부

목록 보기
18/19

바이러스


#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();

        // curr에 연결되어 있는 모든 인접 정점(컴퓨터)에 대해
        for (auto next: adj_list[curr]) {
            if (visited[next]) {
                continue;
            }
            visited[next] = true;
            s.push(next); // 스택에 삽입 -> 1번으로 할거면 여기서 카운트
            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();

        // curr에 연결되어 있는 모든 인접 정점(컴퓨터)에 대해
        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++) { //set 순회
        cout << *iter <<' ';
    }
    return 0;
}
  • 이번주 시간이 빠듯해서 좀 쉬운걸 풀었다 ^^..
  • 중복을 없애고 정렬을 하려면 그냥 set을 사용하면 된다.
  • set은 랜덤접근이 안되니까 iter쓰는거만 안까먹으면 끝!
profile
새싹 백엔드 개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN