프로그래밍

www.acmicpc.net/problem/6497

[난이도] Gold4

[유형] MST (크루스칼)

[풀이]

Kruskal 알고리즘을 이용하여 MST를 구함 주의할점 1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료) 2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.Kruskal 알고리즘을 이용하여 MST를 구함
주의할점
1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료)
2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 2e5;
int N,M,uf[mx];
struct P{
    int a,b,c;
};
vector<P> v;
bool cmp(P& a,P& b){
    return a.c < b.c;
}
int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}

int main(){
    while(1){
        int t=0;
        v.clear();
        scanf("%d%d",&N,&M);
        if(N==0&&M==0) return 0;
        for(int i=0;i<M;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            t+=c;
            v.push_back({a,b,c});
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<N;i++) uf[i]=i;
        int ans =0,cnt=0;
        for(int i=0;i<v.size();i++){
            if(merge(v[i].a,v[i].b)){
                ans+=v[i].c;
                if(++cnt==N-1) break;
            }
        }
        printf("%d\n",t-ans);
    }
}

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

www.acmicpc.net/problem/6087

[난이도] Gold4

[유형] BFS

[풀이]

visit[y][x][d] = y,x에 d방향인 상태로 가기 위해 필요한 최소 거울 개수로
정의하여 BFS를 돌린다. queue에는 y,x,k,d를 모두 넣어줘야 한다.
(k==현재까지 사용한 거울 개수)

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
char map[100][100];
int dy[4] = {-1,1,0,0},ans=1e9;
int dx[4] = {0,0,1,-1};
int H,W,sy=-1,sx,ey,ex,visit[100][100][4];
struct P{
    int y,x,k,d;
};
int main(){
    scanf("%d%d",&W,&H);
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            for(int d=0;d<4;d++) visit[i][j][d]=9e8;
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='C'){
                if(sy==-1) sy=i,sx=j;
                else ey=i,ex=j;
            }
        }
    }
    queue<P> q;
    for(int i=0;i<4;i++) q.push({sy,sx,0,i});
    
    while(!q.empty()){
        P qf = q.front(); q.pop();
        if(qf.y==ey&&qf.x==ex) ans = min(ans,visit[ey][ex][qf.d]);
        for(int i=0;i<4;i++){
            int ny = qf.y+dy[i];
            int nx = qf.x+dx[i];
            if(ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx]=='*') continue; 
            if(qf.d/2!=i/2){
                if(qf.k+1 < visit[ny][nx][i]) {
                    q.push({ny,nx,qf.k+1,i});
                    visit[ny][nx][i] = qf.k+1;
                }
            }else if(qf.d==i){
                if(qf.k < visit[ny][nx][i]) {
                    q.push({ny,nx,qf.k,i});
                    visit[ny][nx][i] = qf.k;
                }               
            }
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/4386

[난이도] Gold4

[유형] MST (크루스칼)

[풀이]

모든 좌표들간의 거기를 계산하여 저장 한 뒤 크루스칼 알고리즘을 이용하여 MST를 구하면 된다.

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct eg{
    int a,b;
    double cost;
};
vector<eg> v;
int N,uf[100];
double x[100],y[100];

bool cmp(eg& a,eg& b){
    return a.cost < b.cost;
}

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

bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%lf%lf",&x[i],&y[i]);
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            double dist = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            v.push_back({i,j,dist});
        }
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<N;i++) uf[i] = i;
    int cnt = 0;
    double ans = 0;
    for(int i=0;;i++){
        if(merge(v[i].a,v[i].b)){
            ans+=v[i].cost;
            if(++cnt==N-1) break;
        }
    }
    printf("%f",ans);
}

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

www.acmicpc.net/problem/2698

[난이도] Gold4

[유형] DP

[풀이]

dp[n][k][f] : 첫 자리가 f로 시작하면서 크기가 n이면서 비트의 개수가 k인
수열의 개수.
f==1 : dp[n][k][f] = dp[n-1][k][0]+dp[n-1][k-1][1] (첫 자리수가 1이므로
n-1크기의 수열도 1 로 시작하면 k를 1개 줄일 수 있다.)
f==0 : dp[n][k][f] = dp[n-1][k][1]+dp[n-1][k][0]

종료조건은 n이 1씩 감소하는게 보장되므로 n==2인 경우로 처리한다.

#include <cstdio>
#include <cstring>
using namespace std;
int tc,N,K,dp[102][101][2];
int sol(int n,int k,int f){
    if(k<0) return 0;
    if(n==2){
        if(f==1) {
            if(k<2) return 1;
        }else{
            if(k==0) return 2;
        }
        return 0;
    }
    int& ret = dp[n][k][f];
    if(ret!=-1) return ret;
    ret = 0;
    if(f==0) ret += sol(n-1,k,1)+sol(n-1,k,0); 
    else ret += sol(n-1,k-1,1)+sol(n-1,k,0);
    return ret;
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&N,&K);
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(N+1,K,0));
    }
}

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

www.acmicpc.net/problem/2473

[난이도] Gold4

[유형] 이분탐색

[풀이]

a+b+C의 절댓값이 0에 가장 가까운 a,b,c를 찾는 문제
N이 5000이므로 N^3으로 풀수가 없다. => 이분탐색 이용
a,b를 결정하고 (N^2) 그 a,b일 때 가장 최적의 c를 이분탐색으로
찾는다(lgN).
s=a+b 일때 0~N-1중 -s의 lower_bound를 찾는다. lower_bound의 위치가
idx이고 a[idx] != -s인 경우에는 idx-1이 최적일수도 있다.
또한 a[idx] == s이어도 idx가 a또는 b인 경우에는 최적이 될 수 없다.
그러므로 넉넉하게 idx-5 ~ idx+5까지 체크하면서 a,b가 아니면서 절댓값이
최소가 되는 c를 찾아야 한다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int N,a[5000],r[3];
ll mxN = 9e10;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);

    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            ll s = a[i]+a[j];
            int idx = lower_bound(a,a+N,-s)-a;
            for(int k=idx-5;k<idx+5;k++){
                if(k<0||k>=N||k==i||k==j) continue;
                ll ss = abs(s+a[k]);
                if(ss < mxN){
                    mxN = ss;
                    r[0]=i,r[1]=j,r[2]=k;
                }
            }
        }
    }
    sort(r,r+3);
    for(int i=0;i<3;i++) printf("%d ",a[r[i]]);
}

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

www.acmicpc.net/problem/2458

[난이도] Gold4

[유형] DFS

[풀이]

in,out 배열을 만들고 각 점에서 DFS를 해서 방문할 수 있는 점의 개수를
out에, DFS중 어떤 점을 방문할때 그 점의 in값을 1씩 증가 시킨다.
in[i]+out[i]==N인 점이 정답인 점들이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,in[501],out[501],ans;
vector<int> adj[501];
bool visit[501];
int dfs(int n){
    visit[n] = 1;
    int ret = 1;
    for(int nxt : adj[n]){
        if(!visit[nxt]){
            in[nxt]++;
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        out[i] = dfs(i);
    }
    for(int i=1;i<=N;i++) if(in[i]+out[i]==N) ans++;
    printf("%d",ans);
}

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

www.acmicpc.net/problem/2239

[난이도] Gold4

[유형] 백트래킹

[풀이]

81개중 빈칸에 대해 1~9의 숫자를 넣어보면서 조건에 맞는지 체크해간다.

#include <cstdio>
using namespace std;
int map[9][9],ok;
bool check(int y,int x,int k){
    for(int i=0;i<9;i++) {
        if(map[y][i]==k || map[i][x]==k) return 0;
    }
    int yy = (y/3)*3, xx=(x/3)*3;
    for(int i=yy;i<yy+3;i++)
        for(int j=xx;j<xx+3;j++) if(map[i][j]==k) return 0;
    
    return 1;
}
void sol(int y,int x){
    if(ok) return;
    if(y==9) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) printf("%d",map[i][j]);
            puts("");
        }
        ok = 1;
        return;
    }
    if(map[y][x]){
        if(x==8) sol(y+1,0);
        else sol(y,x+1);
    }else{
        for(int i=1;i<10;i++){
            if(check(y,x,i)){
                map[y][x] = i;
                if(x==8) sol(y+1,0);
                else sol(y,x+1);
                map[y][x] = 0;
            }
        }
    }
}
int main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++) scanf("%1d",&map[i][j]);
    sol(0,0);
}

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

www.acmicpc.net/problem/2234

[난이도] Gold4

[유형] DFS

[풀이]

1. DFS를 돌면서 각 방이 어떤 그룹에 속하는지 나누면서 각 그룹에 몇개의
   방이 있는지를 체크한다.
2. 모든 방을 순회하면서 동,서,남,북 방향을 체크해 다른 그룹이 있으면
   현재 방의 개수 + 현재 체크중인 인접한 방의 개수를 더해 답을
   갱신해준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,map[50][50],g,grp[2501],mxR,mxS;
int visit[50][50];
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};
int dfs(int y,int x){
    visit[y][x] = g;
    int ret = 1;
    for(int i=0;i<4;i++){
        if((map[y][x] & (1<<i))==0){
            int ny = y+dy[i], nx = x+dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
            ret+=dfs(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j]){
                g++;
                grp[g] = dfs(i,j);
                mxR = max(mxR,grp[g]);
            }
        }
    }
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            for(int i=0;i<4;i++){
                if((map[y][x] & (1<<i))>0){
                    int ny = y+dy[i], nx = x+dx[i];
                    if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                    if(visit[ny][nx] != visit[y][x]) mxS = max(mxS,grp[visit[ny][nx]]+grp[visit[y][x]]);
                }
            }
        }
    }
    printf("%d\n%d\n%d",g,mxR,mxS);
}

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