22.09.08. 풀었던 문제들

백준 단계별 31 MST

2887 SVEMIR

 MST 문제이긴 한데, 단순히 MST로 풀면 안 되는 문제이다. 처음에 주어진 vertex의 개수가 10만 개이기 때문에, 이들 사이의 모든 edge를 고려한다면 10^2이 되어 메모리초과, 또는 시간 초과가 나게 된다.

 따라서 규칙을 찾아서 풀어야 하는 문제였는데, 이 문제에서 dist는 min(x1-x2, y1-y2, z1-z2)이기 때문에 각 vertex 좌표를 입력받고, 정렬하고, 인접한 값의 차이로만 edge를 구성하면 된다. 왜냐하면, point가 a b c 순서일 때 kruskal의 정의 상 smallest edge부터 사용하기 때문에 b - a, c - b를 사용한다. 이 때 a -> c는 a -> b -> c로 표현되기 때문에 a -> c의 edge를 고려할 필요가 없게 되므로, 3n이 된다.

ll Parent[100001], Rank[100001];
ll answer = 0;

ll Find(ll v){
    if(v == Parent[v]) return v;
    Parent[v] = Find(Parent[v]);
    return Parent[v];
}

void Union(ll x, ll y){
    ll rx = Find(x), ry = Find(y);
    if(rx == ry) return;
    if(Rank[rx] < Rank[ry]){
        Parent[rx] = ry;
    }
    else{
        Parent[ry] = rx;
        if(Rank[rx] == Rank[ry]){
            Rank[rx]++;
        }
    }
}

struct diff{
    ll dist, u, v;
};

bool cmp(diff&a, diff&b){
    return a.dist < b.dist;
}

void solve(){
	ll N; cin>>N;

    /*
        x좌표, y좌표, z좌표로 정렬 한 후 인접한 값의 차이로만 edge를 구성한다.
        point가 a b c 순서일 때 kruskal의 정의 상 smallest edge부터 사용하기 때문에
        b - a, c - b를 사용한다.
        a -> c는 a -> b -> c로 표현되기 때문에 a -> c의 edge를 고려할 필요가 없다.
    */

    // push each axis coordinate
    vector<pll> Xs(N), Ys(N), Zs(N); // .first : K value of index i, .second : index
    for(int i = 0; i<N; i++){
        cin>>Xs[i].first>>Ys[i].first>>Zs[i].first;
        Xs[i].second = i;
        Ys[i].second = i;
        Zs[i].second = i;
    }
    sort(Xs.begin(), Xs.end(), less<pll>());
    sort(Ys.begin(), Ys.end(), less<pll>());
    sort(Zs.begin(), Zs.end(), less<pll>());

    // push minimum difference of each axis coordinate
    vector<diff> diffs;
    diff temp;
    for(int i = 0; i<N-1; i++){
        temp.dist = Xs[i+1].first - Xs[i].first;
        temp.u = Xs[i+1].second; temp.v = Xs[i].second;
        diffs.push_back(temp);

        temp.dist = Ys[i+1].first - Ys[i].first;
        temp.u = Ys[i+1].second; temp.v = Ys[i].second;
        diffs.push_back(temp);

        temp.dist = Zs[i+1].first - Zs[i].first;
        temp.u = Zs[i+1].second; temp.v = Zs[i].second;
        diffs.push_back(temp);
    }
    sort(diffs.begin(), diffs.end(), cmp);

    for(int i = 0; i<=N; i++){
        Parent[i] = i;
        Rank[i] = 0;
    }

    for(diff elem : diffs){
        if(Find(elem.u) != Find(elem.v)){
            Union(elem.u, elem.v);
            answer += elem.dist;
        }
    }

    cout<<answer;
}

 

17472 다리 만들기 2

 구현이 빡셌던 문제. MST 자체의 개념은 어렵지 않으나 n by m의 board에서 모든 island를 찾고, 그 island 사이의 edge를 찾는 게 어려웠다.

// 입출력 정보
int N, M;
vector<vector<int>> boards, visited;
int INF = 987654321;

// 섬 정보
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
vector<set<pii>> islands;
bool in_range(int r, int c){
    if(0 <= r && r < N && 0 <= c && c < M) return true;
    return false;
}
void DFS(int r, int c, int island_num){ // DFS하고 섬 번호 붙임
    bool moveable = false;
    visited[r][c] = true;
    islands.back().insert({r, c});
    boards[r][c] = island_num;
    for(int d = 0; d<4; d++){
        int nr = r + dr[d];
        int nc = c + dc[d];
        // in range && ground && unvisited
        if(in_range(nr, nc) && boards[nr][nc] == 1 && visited[nr][nc] == false){
            moveable = true;
            DFS(nr, nc, island_num);
        }
    }

    if(!moveable){
        return;
    }
}

// bridge 정보
vector<vector<int>> edges;
void radial(int r, int c){ // r, c 기준으로 십자 방사.
// 방사 중, cur_island와 같다면 skip, 0이 아니고 다른 island고 length가 2보다 크거나 같아야 넣어 줌.
    int cur_island_num = boards[r][c];
    for(int d = 0; d<4; d++){
        int nr = r, nc = c;
        int cnt = -1;
        while(1){
            nr += dr[d]; nc += dc[d]; // move
            cnt++;
            if(!in_range(nr, nc)){ // if out of range, break
                break;
            }
            if(boards[nr][nc] == cur_island_num) break;
            else if(boards[nr][nc] != 0) { // find next island
                if(cnt < 2) break;
                edges[cur_island_num][boards[nr][nc]] = min(edges[cur_island_num][boards[nr][nc]], cnt);
                break;
            }
        }
    }
}

// mst 위한 함수
struct cmp{
    bool operator()(pii&a, pii&b){
        if(a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    }
};

void solve(){
    // get input
	cin>>N>>M;
    boards.resize(N, vector<int>(M));
    visited.resize(N, vector<int>(M, false));
    for(int r = 0; r<N; r++){
        for(int c = 0; c<M; c++){
            cin>>boards[r][c];
        }
    }

    // get island from input
    int num = 1;
    for(int r = 0; r<N; r++){
        for(int c = 0; c<M; c++){
            if(boards[r][c] == 1 && visited[r][c] == false){
                islands.push_back({});
                DFS(r, c, num);
                num++;
            }
        }
    }

    // 각 island의 다리
    edges.resize(islands.size()+1, vector<int>(islands.size()+1, INF));
    for(int i = 0; i<islands.size(); i++){ // for all island
        for(pii point : islands[i]){ // for all points in island
            radial(point.first, point.second); // 십자형 방사 전개
        }
    }

    // MST 구성 with prim
    set<int> mst;
    priority_queue<pii, vector<pii>, cmp> pq; // .first : index, second : weight
    int answer = 0;
    mst.insert(1);
    for (int i = 0; i <= islands.size(); i++){
        if (i == 0 || edges[1][i] == INF || edges[1][i] < 2) continue;
        pq.push({i, edges[1][i]});
    }
    while(!pq.empty() && mst.size() != islands.size()){
        int top = pq.top().first, weight = pq.top().second; pq.pop();
        if(weight < 2 || weight == INF) continue;
        if(mst.find(top) == mst.end()){ // not found in mst then push
            answer += weight;
            mst.insert(top);
            for(int i = 0; i<=islands.size(); i++){
                if(i == 0 || i == top || edges[top][i] == INF || edges[top][i] < 2) continue;
                pq.push({i, edges[top][i]});
            }
        }
    }

    if(mst.size() == islands.size()) cout<<answer;
    else cout<<-1;
}