# BFS
각 지도를 돌면서 BFS 알고리즘을 실행시켜주면된다.
이미 이전에 방문한 단지는 방문하지 않는다!
#include <iostream> #include <algorithm> #include <vector> #include <queue> #define MAX 30 #define INF 2123456789 using namespace std; typedef long long ll; typedef pair<int,int> pi; // map[0][][]에는 이전에 방문 여부를 저장하고 // map[1][][]에는 집의 유무를 저장한다. int n, map[2][MAX][MAX]; // 4방향에 대해서 탐색한다. int dy[4]={0,1,0,-1},dx[4]={1,0,-1,0}; vector<int> ans; char str[MAX]; // bfs 알고리즘 void bfs(int y,int x) { int cnt=1; queue<pi> q; q.push({y,x}); while(!q.empty()) { pi tmp = q.front(); q.pop(); // 4방향에 대해 탐색한다. for(int i=0;i<4;i++) { y=tmp.first+dy[i],x=tmp.second+dx[i]; // 이전에 방문하지 않았고, 집이있다면 if(map[0][y][x]==0&&map[1][y][x]==1) { // 방문표시를 해준다. map[0][y][x]=1; // 큐에 넣어준다. q.push({y,x}); cnt++; } } } // 벡터에 집의 갯수를 넣어준다. ans.push_back(cnt); } int main() { // 초기화 및 입력 fill_n(&map[0][0][0],2*MAX*MAX,0); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",str); for(int j=0;j<n;j++) map[1][i+1][j+1]=str[j]-'0'; } // 각 좌표에 방문한다. for(int i=1;i<=n;i++) { for (int j = 1; j <= n; j++) { // 이전에 방문하지 않았고, 집이있다면 if (map[0][i][j] == 0 && map[1][i][j] == 1) { map[0][i][j] = 1; bfs(i, j); } } } // 정렬 하여준다. sort(ans.begin(),ans.end()); // 전체 단지수를 출력하여준다. printf("%d\n",ans.size()); // 집의 갯수를 출력하여준다. for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]); return 0; }
'IT > BOJ' 카테고리의 다른 글
백준(BOJ) 13458 시험 감독 * (0) | 2019.03.18 |
---|---|
백준(BOJ) 2870 수학숙제 * (0) | 2019.03.17 |
백준(BOJ) 2665 미로만들기 * (0) | 2019.03.13 |
백준(BOJ) 16189 Repetitive Palindrome * (0) | 2018.10.07 |
백준(BOJ) 16190 Rising Sun ** (0) | 2018.10.07 |