백준: Class 5 - 2239, 2473, 4386

</br> 클래스 5 계속
</br>

2239: 스도쿠

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

#include <bits/stdc++.h>

using namespace std;

int sdoku[9][9];
int zeros;
bool solved;

void printsdoku(){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            cout << sdoku[i][j];
        }
        cout << endl;
    }
}
bool check(int x, int y, int k){
    for(int i = x/3*3; i < x/3*3+3; i++){
        for(int j = y/3*3; j < y/3*3+3; j++){
            if( sdoku[i][j] == k ) return false;
        }
    }
    for(int i = 0; i < 9; i++){
        if( sdoku[x][i] == k ) return false;
        if( sdoku[i][y] == k ) return false;
    }
    return true;
}

void func(int x, int z){
    for(int i = x; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if( sdoku[i][j] ) continue;
            for(int k = 1; k <= 9; k++){
                if( check(i, j, k) ){
                    sdoku[i][j] = k;
                    if( z == zeros ){
                        printsdoku();
                        solved = true;
                        return;
                    }
                    func(i, z+1);
                    if( solved ) return;
                    sdoku[i][j] = 0;
                }
            }
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    for(int i = 0; i < 9; i++){
        string s;
        cin >> s;
        for(int j = 0; j < 9; j++){
            sdoku[i][j] = s[j]-'0';
            if( sdoku[i][j] == 0 ) zeros++;
        }
    }
    solved = false;
    func(0, 1);
}

백트래킹으로 구현 문제다
컴퓨터가 편한 이유는 머리 안 쓰고 다 대입해 보기 때문
(0,0)부터 쭉 1~9까지 넣어 보고, 안 되면 되돌아 오고, 되면 출력하고 끝내면 된다
bool 변수인 solved는 꼭 필요하다

000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000

이런 거 있으면 가능한 대로 계속 다 해보기 때문에 한 번 풀면 멈추도록 해준다.
</br>

2473: 세 용액

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

    long long ans = 3000000001;
    vector<int> v(3);
    sort(ph, ph+n);

    for(int i = 0; i < n; i++){
        int l = 0, r = n-1;
        while( l < r ){
            if( l == i ) l++;
            if( r == i ) r--;
            if( l == r ) break;
            long long now = ph[l] + ph[r] + ph[i];
            if( abs(now) < ans ){
                v[0] = ph[i];
                v[1] = ph[l];
                v[2] = ph[r];
                ans = abs(now);
            }
            if( ans == 0 ) break;
            if( now < 0 ) l++;
            else r--;
        }

    }
    sort(v.begin(), v.end());

    cout << v[0] << ' ' << v[1] << ' ' << v[2] << endl;

저번엔 두 용액(2467: 용액, https://cyj893.github.io/algorithm/Algorithm17/)에 투 포인터였으니 이번엔 쓰리 포인터일까
비슷하다. 용액 하나를 정하고, 투 포인터를 돌리는 걸 한 번 돌면 된다.
</br>

4386: 별자리 만들기

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

double dist(pair<double, double> &p1, pair<double, double> &p2){
    double t1 = p1.first - p2.first;
    double t2 = p1.second - p2.second;
    return sqrt(t1*t1 + t2*t2);
}

struct UnionFind{
    vector<int> parent, ran;
    UnionFind(int n) : parent(n), ran(n, 1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    int f(int u){
        if( u == parent[u] ) return u;
        parent[u] = f(parent[u]);
        return parent[u];
    }
    bool merg(int u, int v){
        u = f(u); v = f(v);
        if( u == v ) return false;
        if( ran[u] > ran[v] ) swap(u, v);
        parent[u] = v;
        ran[v] += ran[u];
        ran[u] = 0;
        return true;
    }
};

// in main()
    vector< pair<double, double> > v;
    for(int i = 0; i < n; i++){
        double a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
    priority_queue<T, vector<T>, greater<>> pq;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            double d = dist(v[i], v[j]);
            pq.push(make_tuple(d, i, j));
        }
    }
    double ans = 0.0;
    UnionFind uf = UnionFind(n);
    while( pq.size() ){
        double w = get<0>(pq.top());
        double x = get<1>(pq.top());
        double y = get<2>(pq.top());
        pq.pop();

        if( uf.merg(x, y) ){
            ans += w;
        }

    }
    cout << ans << endl;

크루스칼 알고리즘을 복습할 기회가 바로 또 나왔다
외우기 좋네
일단 별들을 입력 받고, 별들 두 개 사이의 거리를 우선순위 큐에 넣어주면 된다
</br>

---

크루스칼도 한 번 아니까 나오니까 좋다
</br>