ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ] #17472 _ 다리 만들기 2
    Problem Solving/BOJ 2019. 10. 22. 22:58
    728x90

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

     

    17472번: 다리 만들기 2

    첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

    www.acmicpc.net

    map의 정보를 0과 1로만 준다.

    따라서, 바다를 각 숫자로 만들어주고, 최단 거리를 구한 후, 모두 연결되어 있는지 확인하였다.

     

    getNewMap() 함수를 통해 아래와 같이 바다를 각 숫자로 변경해주었다.

     

    getDistMap() 함수를 통해 각 바다의 거리를 구해주었다.

     

    최단거리를 구하고, 모두 연결되어 있는지 확인하기 위해 크루스칼 알고리즘을 사용하였다.

     

    크루스칼 알고리즘 (Kruskal's Algorithm) 이란?
    가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

    [참고] https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #define MAX 10
    #define INF 99999999
    
    using namespace std;
    typedef struct sea {
    	int a, b, d;
    }Sea;
    
    int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
    int N, M, island_cnt;
    int map[MAX][MAX], new_map[MAX][MAX], dist[7][7], chk[7];
    vector<pair<int, int> > island[6];
    
    void initDist();
    int solve();
    void getNewMap();
    void getDistMap();
    int getMinDist();
    int findParent(int idx);
    int checkConnect();
    bool cmp(const Sea& a, const Sea& b);
    int main() {
    	scanf("%d %d", &N, &M);
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < M; j++) {
    			scanf("%d", &map[i][j]);
    		}
    	}
    
    	printf("%d\n", solve());
    
    	return 0;
    }
    
    void initDist() {
    	for (int i = 0; i < 7; i++) {
    		for (int j = 0; j < 7; j++) dist[i][j] = INF;
    	}
    }
    
    int solve() {
    	initDist();
    	getNewMap();
    	getDistMap();
    	return getMinDist();
    }
    
    void getNewMap() {
    	queue<pair<int, int> > q;
    	int check[MAX][MAX] = { 0, }, tmp_y, tmp_x, y, x;
    
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < M; j++) {
    			if (map[i][j]) {
    				if (check[i][j]) continue;
    				q.push(make_pair(i, j));
    				island[island_cnt].push_back(make_pair(i, j));
    				new_map[i][j] = island_cnt + 1;
    				check[i][j] = 1;
    
    				while (!q.empty()) {
    					y = q.front().first;
    					x = q.front().second;
    					q.pop();
    
    					for (int k = 0; k < 4; k++) {
    						tmp_y = y + dy[k];
    						tmp_x = x + dx[k];
    						if (tmp_x < 0 || tmp_y < 0 || tmp_x >= M || tmp_y >= N) continue;
    						if (check[tmp_y][tmp_x]) continue;
    						if (!map[tmp_y][tmp_x]) continue;
    						q.push(make_pair(tmp_y, tmp_x));
    						island[island_cnt].push_back(make_pair(tmp_y, tmp_x));
    						new_map[tmp_y][tmp_x] = island_cnt + 1;
    						check[tmp_y][tmp_x] = 1;
    					}
    				}
    				island_cnt++;
    			}
    		}
    	}
    }
    
    void getDistMap() {
    	int d, tmp_y, tmp_x, val;
    
    	for (int i = 0; i < island_cnt; i++) {
    		for (int j = 0; j < island[i].size(); j++) {
    			tmp_y = island[i][j].first;
    			tmp_x = island[i][j].second;
    			val = new_map[island[i][j].first][island[i][j].second];
    			for (int k = 0; k < 4; k++) {
    				d = 0;
    				while (1) {
    					tmp_y += dy[k];
    					tmp_x += dx[k];
    					if (tmp_y < 0 || tmp_x < 0 || tmp_y >= N || tmp_x >= M) break;
    					if (new_map[tmp_y][tmp_x] == val) break;
    					if (new_map[tmp_y][tmp_x] > 0) {
    						if (d == 1) break;
    						dist[val][new_map[tmp_y][tmp_x]] = min(dist[val][new_map[tmp_y][tmp_x]], d);
    						dist[new_map[tmp_y][tmp_x]][val] = dist[val][new_map[tmp_y][tmp_x]];
    						break;
    					}
    					d++;
    				}
    			}
    			
    		}
    	}
    }
    
    int getMinDist() {
    	vector<Sea> v;
    
    	for (int i = 1; i <= island_cnt; i++) {
    		chk[i] = i;
    		for (int j = i + 1; j <= island_cnt; j++) {
    			if (dist[i][j] == INF) continue;
    			v.push_back({ i,j,dist[i][j] });
    		}
    	}
    	sort(v.begin(), v.end(), cmp);
    
    	int result = 0, tmp_a, tmp_b;
    	for (int i = 0; i < v.size(); i++) {
    		tmp_a = findParent(v[i].a);
    		tmp_b = findParent(v[i].b);
    		if (tmp_a == tmp_b) continue;
    		result += v[i].d;
    		chk[tmp_b] = tmp_a;
    	}
    
    	if (checkConnect()) return result;
    	else return -1;
    }
    
    int findParent(int idx) {
    	while (idx != chk[idx]) idx = chk[idx];
    	return idx;
    }
    
    int checkConnect() {
    	int cmp_val = findParent(chk[1]);
    	for (int i = 2; i <= island_cnt; i++) {
    		if (findParent(i) != cmp_val) return 0;
    	}
    	return 1;
    }
    
    bool cmp(const Sea& a, const Sea& b) {
    	return a.d < b.d;
    }
    반응형

    'Problem Solving > BOJ' 카테고리의 다른 글

    [BOJ] #6086 _ 최대 유량  (0) 2020.03.09
    [BOJ] #7616 _ 교실로 가는 길  (0) 2020.03.09
    [BOJ] #17472 _ 다리 만들기 2  (0) 2019.10.22
    [BOJ] #17471 _ 게리맨더링  (0) 2019.10.22
    [BOJ] #17281 _ 야구  (0) 2019.10.22
    [BOJ] #17144 _ 미세먼지 안녕!  (0) 2019.10.22

    댓글 0

@Jo Grini's Blog