-
섬의 개수 - 4963Algorithm/BOJ 2020. 3. 3. 18:3812345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273//4963 - 섬의 개수#include <iostream>#include <vector>using namespace std;int N, M;int arr[50][50];int sN;int xarr[8] = {-1, -1, -1, 0, 1, 1, 1, 0};int yarr[8] = {-1, 0, 1, 1, 1, 0, -1, -1};struct DisjointSet{vector<int> parent, rank;DisjointSet(int n) : parent(n), rank(n, 1){for(int i = 0; i<n; ++i)parent[i] = i;}int find(int u){if(u == parent[u]) return u;return parent[u] = find(parent[u]);}void merge(int u, int v){u = find(u); v = find(v);if(u == v) return;if(rank[u] > rank[v]) swap(u, v);parent[u] = v;if(rank[u] == rank[v]) ++rank[v];--sN;}};void init(){int x;sN = 1;for(int i = 0; i<N; ++i)for(int j = 0; j<M; ++j){cin >> x;if(x)arr[i][j] = sN++;elsearr[i][j] = 0;}}int main(){ios_base::sync_with_stdio(0); cin.tie(0);for (cin >> M >> N; N; cin >> M >> N){init();DisjointSet set(sN);for(int i = 0; i<N; ++i)for(int j = 0; j<M; ++j)if(arr[i][j])for(int k = 0; k<8; ++k)if(i + xarr[k] >= 0 && i + xarr[k] < N&& j + yarr[k] >= 0 && j + yarr[k] < M)if(arr[i+xarr[k]][j+yarr[k]])set.merge(arr[i][j], arr[i+xarr[k]][j+yarr[k]]);cout << --sN << "\n";}}
cs https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는
www.acmicpc.net
섬의 개수
union-find를 사용해 해결했습니다!
'Algorithm > BOJ' 카테고리의 다른 글
줄 세우기 - 2252 (0) 2020.03.04 플로이드 - 11404 (0) 2020.03.03 행렬 곱셈 순서 - 11049 (0) 2020.03.03 파일 합치기 - 11066 (0) 2020.03.02 가장 긴 바이토닉 부분 수열 - 11054 (0) 2020.03.01