-
[BOJ] #17472 _ 다리 만들기 2Problem Solving/BOJ 2019. 10. 22. 22:58
[다리 만들기 2] https://www.acmicpc.net/problem/17472
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] #17471 _ 게리맨더링 (0) 2019.10.22 [BOJ] #17281 _ 야구 (0) 2019.10.22 [BOJ] #17144 _ 미세먼지 안녕! (0) 2019.10.22 댓글