프로그래밍

www.acmicpc.net/problem/1199

[난이도] Gold4

[유형] 최소 스패닝 트리 (크루스칼)

[풀이] 크루스칼 알고리즘

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct edge{
    int a,b,cost;
};
int V,E,uf[10001];
vector<edge> eg;
bool cmp(edge& a,edge& b){
    return a.cost < b.cost;
}

int find(int a){
    if(uf[a]==a) return a;
    return uf[a] = find(uf[a]);
}

bool merge(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa==pb) return 0;
    uf[pa] = pb;
    return 1;
}
int main(){
    scanf("%d%d",&V,&E);
    for(int i=0;i<E;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        eg.push_back({a,b,c});
    }
    sort(eg.begin(),eg.end(),cmp);
    for(int i=1;i<=V;i++) uf[i] = i;
    int cnt = 0, ans = 0;
    for(int i=0;;i++){
        edge e = eg[i];
        if(merge(e.a,e.b)){
            ans+=e.cost;
            if(++cnt==V-1) break;
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1199.cpp

www.acmicpc.net/problem/11657

[난이도] Gold4

[유형] Bellman-Ford

[풀이]

음의 가중치가 있는데 최단 경로를 구해야 하는 경우는 벨만포드 또는 플로이드 워셜 이용. 벨만포드 : V*E 플로이드 워셜 : V^3이므로 벨만포드를 이용한다. 최단 경로의 간선수는 최대 V-1개이기 때문에 V-1번 루프를 돌면서 최단 경로를 갱신해준다.

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
int N,M;
vector<pair<int,ll>> adj[501];
ll dist[501],inf=1e18;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back({b,c});
    }

    for(int i=1;i<=N;i++) dist[i] = inf;
    dist[1] = 0;
    bool cycle = 0;
    for(int i=0;i<N;i++){
        for(int j=1;j<=N;j++){
            for(auto& p : adj[j]){
                int nxt = p.first, cost=p.second;
                if(dist[j] != inf && dist[nxt] > dist[j]+cost){
                    dist[nxt] = dist[j]+cost;
                    if(i==N-1) cycle = 1;
                }
            }
        }
    }
    if(cycle) puts("-1");
    else{
        for(int i=2;i<=N;i++) printf("%lld\n",dist[i]==inf ? -1 : dist[i]);
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11657.cpp

www.acmicpc.net/problem/11404

[난이도] Gold4

[유형] 플로이드 워셜

[풀이] 플로이드 워셜

#include <cstdio>
#include <algorithm>
int N,M,dist[101][101],INF=9e8;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            dist[i][j] = INF;
            if(i==j) dist[i][j] = 0;
        }
    }
    
    for(int i=0;i<M;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(c < dist[a][b]) dist[a][b] = c;
    }

    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                dist[i][j] = std::min(dist[i][j],dist[i][k]+dist[k][j]); 
            }
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            printf("%d ",dist[i][j]==INF ? 0:dist[i][j]);
        }
        puts("");
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11404.cpp

www.acmicpc.net/problem/10830

[난이도] Gold4

[유형] Divide and Conquer(행렬곱)

[풀이]

1. 구조체 A를 정의하고 연산자 오버로딩을 이용해서 행렬곱 구현. 2. A^2n=A^n*A^n인 행렬의 성질을 이용하여 재귀함수로 정답 도출

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
using vv = vector<vector<ll>>;
int N;
ll B,mod=1000;
struct A{
    vv arr;
    A(){};
    A(vv arr):arr(arr){};
    A operator*(A& a){
        vv tmp = arr;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                tmp[i][j]=0;
                for(int k=0;k<N;k++){
                    tmp[i][j] += arr[i][k]*a.arr[k][j];
                    tmp[i][j]%=mod;
                }
            }
        }
        return A(tmp);
    }
};
A base;
void print(A& a){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%lld ",a.arr[i][j]);
        }
        puts("");
    }
}
A sol(ll n){
    if(n==1) return base;
    A u = sol(n/2);
    u=u*u;
    if(n%2) u=u*base;
    return u;
}
int main(){
    scanf("%d%lld",&N,&B);
    vv v;
    v.resize(N);
    for(int i=0;i<N;i++){
        ll t;
        for(int j=0;j<N;j++){
            scanf("%lld",&t);
            v[i].push_back(t%mod);
        }
    }
    base = A(v);
    A ret = sol(B);
    print(ret);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10830.cpp

www.acmicpc.net/problem/1043

[난이도] Gold4

[유형] DFS

[풀이]

지민이는 진실을 아는 사람이 있는 파티에서는 거짓말을 못한다. 어떤 파티에서 진실을 아는 사람이 있어서 진실을 말하면 그 파티에 참여한 진실을 모르는 사람이 참여한 모든 파티에서도 거짓말을 할 수 없다. 즉, 지민이가 진실을 말한 파티에 있는 모든 사람들은 진실을 아는거나 마찬가지이다. 이 성질을 이용하여 진실을 아는 사람들을 DFS를 이용하여 갱신해주면 답을 구할 수 있다.

#include <cstdio>
#include <vector>
using namespace std;
int N,M;
vector<int> pp[51],pty[51],tp;
bool visit[51];
void dfs(int n){
    visit[n] = 1;
    for(auto ptn : pp[n]){
        for(auto p : pty[ptn]){
            if(!visit[p]) dfs(p);
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    int t,v;
    scanf("%d",&t);
    for(int i=0;i<t;i++) {
        scanf("%d",&v);
        tp.push_back(v);
    }
    for(int i=1;i<=M;i++){
        scanf("%d",&t);
        for(int j=0;j<t;j++){
            scanf("%d",&v);
            pty[i].push_back(v);
            pp[v].push_back(i);
        }
    }

    for(auto a : tp) dfs(a);
    int ans = 0;
    for(int i=1;i<=M;i++){
        bool ok = 1;
        for(auto p : pty[i]) {
            if(visit[p]){
                ok = 0;
                break;
            }
        }
        if(ok) ans++;
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1043.cpp

www.acmicpc.net/problem/1022

[난이도] Gold4

[유형] 구현

[풀이]

소용돌이의 오른쪽 아래 꼭지점은 (2*n+1)^2 라는점을 이용

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int r1,r2,c1,c2;

int getV(int r,int c){

    int a = max(abs(r),abs(c));
    int v = (2*a+1);
    v*=v;
    if(a==r) return v-(a-c);
    v-=2*a;
    if(-a==c) return v-(a-r);
    v-=2*a;
    if(-a==r) return v-(a+c);
    v-=2*a;
    return v-(a+r);
}
int main(){
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    int k = 0;
    for(int i=r1;i<=r2;i++){
        for(int j=c1;j<=c2;j++){
            int v = getV(i,j);
            k = max(v,k);
        }
    }

    int t = 0;
    while(k>0){
        t++;
        k/=10;
    }
    for(int i=r1;i<=r2;i++){
        for(int j=c1;j<=c2;j++){
            printf("%*d ",t,getV(i,j));
        }
        puts("");
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1022.cpp

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

[풀이] DP

dp 정의 : dp[n] = n원을 동전으로 교환하는 경우의 수.

 i : 0 ~ K-1까지 모든 동전 종류를 순회하면서

 i 번째 동전까지 썼을때의 dp[j] (j : T~1) 을 구해준다.

 T부터 거꾸로 하는 이유가 중요한데

1부터 할 경우 dp[1~j-1] 이 dp[j] 에 포함될 수 있기 때문이다.

dp[1~j-1]에는 i번째 동전을 쓰는 경우의 수까지 포함되어 있어서 dp[j]에는 포함되면 안된다.

동전 i를 몇개 선택할지 정해야 하기 때문에 동전 개수만큼 순회하면서 sum에 더해주고

if(j-sum >= 0 && dp[j-sum] > 0 을 만족하는 k를 찾으면 dp[j]에 dp[j-sum]을 더해주면 된다.

https://github.com/has2/Algorithm/blob/master/boj/RANDOM_PROBLEM/2624.cpp

https://leetcode.com/problems/battleships-in-a-board/

[풀이] BFS

1XN 또는 NX1 모양의 배를 찾는 문제. 

문제의 조건에 배는 인접하지 않고

valid한 map만 주어진다고 했으므로

BFS를 돌면서 찾은 그룹의 개수가 답이다.

https://github.com/has2/Algorithm/blob/master/leetcode/419.%20Battleships%20in%20a%20Board.cpp