[ BOJ 백준 1944번 - 복제 로봇 ] 해설 및 코드

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

목적

복제된 로봇이 모든 열쇠를 찾기 위한 이동 거리의 최소값을 구하자.

 

접근법

1. 시작 지점과 열쇠가 있는 지점들을 정점으로 하는 그래프에서의 MST를 구하는 문제이다.

2. BFS로 정점간의 최단 거리를 구하여 이를 간선에 포함시켜 크루스칼 알고리즘을 적용하자.

3. 주의할 점

• 시작지점도 정점으로 포함하므로 정점의 최대값은 m의 최대값에 1을 더한 값이다.
• 중복 간선을 제외하여 프로그램 실행 시간을 줄이자.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
typedef pair<int,int> pii;
 
struct edge{
    int a,b,c;
    bool operator<(const edge& oth)const{
        return c<oth.c;
    }
}e[251*126];
int n,m,edge_cnt=0,p[251],key[50][50],di[]={0,0,1,-1},dj[]={1,-1,0,0};
 
void findEdge(int i, int j){
    queue<pii> q;q.push({i,j});
    bool vis[50][50]{};vis[i][j]=true;
    int a=key[i][j],c=0;
        
    while(!q.empty()){
        size_t size=q.size();
        f(k,0,size){
            i=q.front().first;j=q.front().second;q.pop();
            int b=key[i][j];
            if(b>a){
                e[edge_cnt].a=a;
                e[edge_cnt].b=b;
                e[edge_cnt++].c=c;
            }
            f(d,0,4){
                int ni=i+di[d],nj=j+dj[d];
                if(vis[ni][nj]||key[ni][nj]==-1)continue;
                vis[ni][nj]=true;
                q.push({ni,nj});
            }
        }
        ++c;
    }
}
 
int find(int x){
    return p[x]<0?x:p[x]=find(p[x]);
}
 
int mst(){
    memset(p, -1, sizeof(p));
    int ret=0,cnt=0;
    sort(e,e+edge_cnt);
    f(i,0,edge_cnt){
        int ra=find(e[i].a),rb=find(e[i].b);
        if(ra==rb)continue;
        p[ra]=rb;
        ret+=e[i].c;
        if(++cnt==m)break;
    }
    return cnt==m?ret:-1;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    int key_no=0;
    f(i,0,n){
        char tmp[51];cin>>tmp;
        f(j,0,n){
            if(tmp[j]!='1'&&tmp[j]!='0')key[i][j]=key_no++;
            else key[i][j]=tmp[j]-'2';
        }
    }
    
    f(i,0,n)f(j,0,n)if(key[i][j]>=0)findEdge(i,j);
    cout<<mst();
    return 0;
}
 
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.