다리 만들기 2 (feat. 백준, 17472번)

다리 만들기 2
https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int arr[10][10], dx[4], dy[4], N, M, parent[7], total_land_cnt, ans;
bool visit[10][10];
vector<tuple<int, int, int>> note;      // 시작 섬, 도착 섬, 거리
vector<int> tmp[7];
bool distance_sort(const tuple<int, int, int>& v1, const tuple<int, int, int>& v2){
    if(get<2>(v1) < get<2>(v2))
        return true;
    return false;
}
int find(register int n){
	if (n == parent[n])
        return n;
	return find(parent[n]);
}
bool union_check(register int p1, register int p2){
	p1 = find(p1);
	p2 = find(p2);
	if (p1 != p2){
		parent[p1] = p2;
        tmp[p1].push_back(p2), tmp[p2].push_back(p1);
		return true;
	}
	return false;	
}
void func1(){
    queue<pair<int, int>> q;
    for(register int i = 0, j, x, y, d, nx, ny; i < N; ++i)
        for(j = 0; j < M; ++j)
            if(arr[i][j] == -1){
                q.push(make_pair(i, j));
                arr[i][j] = ++total_land_cnt;
                while(!q.empty()){
                    x = q.front().first, y = q.front().second; q.pop();
                    for(d = 0; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny] == -1)
                            arr[nx][ny] = total_land_cnt, q.push(make_pair(nx, ny));
                    }
                }
            }
}
void func2(){
    for(register int i = 0, j, d, dist, nx, ny; i < N; ++i)
        for(j = 0; j < M; ++j)
            if(arr[i][j] != 0)
                for(d = 0; d < 4; ++d){
                    dist = 0, nx = i, ny = j;
                    while(true){
                        nx += dx[d], ny += dy[d];
                        if(nx < 0 || nx >= N || ny < 0 || ny >= M || arr[i][j] == arr[nx][ny])
                            break;
                        if(arr[nx][ny]){
                            if(dist >= 2)
                                note.push_back(make_tuple(arr[i][j], arr[nx][ny], dist));
                            break;
                        }
                        ++dist;
                    }
                }
}
void func3(){
    for(auto& p : note){
        auto& start_land = get<0>(p);
        auto& end_land = get<1>(p);
        auto& dist = get<2>(p);
        if(union_check(start_land, end_land))
            ans += dist;
    }
}
bool func4(register int start_land){
    bool visit[7]{false};
    register int cnt = 1;
    queue<int> q;
    q.push(start_land);
    while(!q.empty()){
        auto p = q.front(); q.pop();
        visit[p] = true;
        for(auto& connected_land : tmp[p]){
            if(!visit[connected_land])
                q.push(connected_land), ++cnt;
        }
    }
    if(cnt == total_land_cnt)
        return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    for(register int i = 0; i < 7; ++i)
        parent[i] = i;
    total_land_cnt = ans = 0;
    cin >> N >> M;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < M; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 1)
                arr[i][j] = -1;
        }
    func1();        // 섬마다 고유번호를 붙이기 위한 bfs. 첫번째 섬의 (i, j)는 모두 1을, 두번째 섬의 (i, j)는 모두 2를 삽입
    func2();        // 섬과 섬 사이의 거리를 구함
    sort(note.begin(), note.end(), distance_sort);      // 거리를 기준으로 오름차순 정렬
    func3();        // 크루스칼 알고리즘을 이용한 최소 스패닝 트리 생성 (union_array) 및 섬과 섬 간 최소 거리의 합을 구함
    if(func4(1))    // 그래프 탐색을 통해 이어진 섬과 섬의 개수 및 섬의 총 개수를 구함. 이어진 섬의 총 개수와 func1에서 할당한 섬의 총 개수가 같다면 최소 거리를 출력
        cout << ans;
    else
        cout << -1;
	return 0;
}
// *&)*@*

크루스칼 알고리즘 풀이

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int arr[10][10], dx[4], dy[4], N, M, total_land_cnt, ans;
vector<tuple<int, int, int>> note;      // 시작 섬, 도착 섬, 거리
bool distance_sort(const tuple<int, int, int>& v1, const tuple<int, int, int>& v2){
    if(get<2>(v1) < get<2>(v2))
        return true;
    return false;
}
void func1(){
    queue<pair<int, int>> q;
    for(register int i = 0, j, x, y, d, nx, ny; i < N; ++i)
        for(j = 0; j < M; ++j)
            if(arr[i][j] == -1){
                q.push(make_pair(i, j));
                arr[i][j] = ++total_land_cnt;
                while(!q.empty()){
                    x = q.front().first, y = q.front().second; q.pop();
                    for(d = 0; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny] == -1)
                            arr[nx][ny] = total_land_cnt, q.push(make_pair(nx, ny));
                    }
                }
            }
}
void func2(){
    for(register int i = 0, j, d, dist, nx, ny; i < N; ++i)
        for(j = 0; j < M; ++j)
            if(arr[i][j] != 0)
                for(d = 0; d < 4; ++d){
                    dist = 0, nx = i, ny = j;
                    while(true){
                        nx += dx[d], ny += dy[d];
                        if(nx < 0 || nx >= N || ny < 0 || ny >= M || arr[i][j] == arr[nx][ny])
                            break;
                        if(arr[nx][ny]){
                            if(dist >= 2)
                                note.push_back(make_tuple(arr[i][j], arr[nx][ny], dist)), note.push_back(make_tuple(arr[nx][ny], arr[i][j], dist));
                            break;
                        }
                        ++dist;
                    }
                }
}
bool func3(register int land){
    bool visit[7]{false};
    register int dist = 0;
    visit[land] = true;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;      // 거리, 도착 섬
    for(auto& p : note){
        auto& start_land = get<0>(p);
        if(start_land != land)
            continue;
        auto& end_land = get<1>(p);
        dist = get<2>(p);
        q.push(make_pair(dist, end_land));
    }
    while(!q.empty()){
        auto p = q.top(); q.pop();
        land = p.second, dist = p.first;
        if(visit[land])
            continue;
        visit[land] = true;
        ans += dist;
        for(auto& p : note){
            auto& start_land = get<0>(p);
            if(start_land != land)
                continue;
            auto& end_land = get<1>(p);
            auto& dist = get<2>(p);
            q.push(make_pair(dist, end_land));
        }
    }
    register int cnt = 0;
    for(auto& v : visit)
        if(v)
            ++cnt;
    if(cnt == total_land_cnt)
        return true;
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    total_land_cnt = ans = 0;
    cin >> N >> M;
    for(register int i = 0, j; i < N; ++i)
        for(j = 0; j < M; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 1)
                arr[i][j] = -1;
        }
    func1();        // 섬마다 고유번호를 붙이기 위한 bfs. 첫번째 섬의 (i, j)는 모두 1을, 두번째 섬의 (i, j)는 모두 2를 삽입
    func2();        // 섬과 섬 사이의 거리를 구함
    sort(note.begin(), note.end(), distance_sort);      // 거리를 기준으로 오름차순 정렬
    if(func3(1))    // 프림 알고리즘을 통한 최소 스패닝 트리(MST) 생성 및 최소 거리의 합과 연결된 섬의 총 개수를 구함
        cout << ans;
    else
        cout << -1;
	return 0;
}
// *&)*@*

프림 알고리즘 풀이

 

반응형

1. 2146번 "다리 만들기" 의 업그레이드 버전이라고 볼 수 있습니다.
2. 섬에서 다른 섬으로의 체크가 한쪽 방향의 진행이므로 이를 유의해야 합니다.
3. 섬 1 - 섬 2 가 직접 연결되지 않았더라도 섬 1 - 섬 4 - 섬 2 와 같이 연결된다면 이를 최소 스패닝 트리을 통해 연결시켜 줍니다. 이때 크루스칼 알고리즘과 프림 알고리즘 모두 사용하여 풀이해보았습니다.
4. 섬과 섬이 연결되었는지는 그래프 탐색을 통해 구할 수 있고 이때의 총 개수가 섬의 총 개수와 같은지 확인해야 합니다.