• Home
  • About
    • Jiwon Jeong photo

      Jiwon Jeong

      끊임없이 배우며 성장하는 엔지니어

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • All Categories
  • Projects

정수 삼각형

07 Apr 2021

Reading time ~1 minute

백준 2667- 단지번호붙이기 (https://www.acmicpc.net/problem/2667)

풀이

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int a[30][30];
int group[30][30];
int dx[] = {1, 0, -1, 0}; //동서남북
int dy[] = {0, 1, 0, -1};
int n;
int ans[25*25];

void bfs(int x, int y, int cnt){
    queue <pair<int,int>> q;
    q.push(make_pair(x,y));
    group[x][y]=cnt;

    while(!q.empty()){
        x = q.front().first;
        y= q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<n){
                if(a[nx][ny]==1 && group[nx][ny]==0){
                    q.push(make_pair(nx,ny));
                    group[nx][ny]=cnt;
                }
            }
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
        }
    }
    int cnt=0;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(a[i][j]==1 && group[i][j]==0){ //새롭게 단지를 돌 준비
                bfs(i, j, cnt++);
            }
        }
    }
    printf("%d\n",cnt);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            ans[group[i][j]]+=1; //단지별 속하는 집 수 증가
        }
    }
    sort(ans+1, ans+cnt+1);
    for (int i=1; i<=cnt; i++) {
        printf("%d\n",ans[i]);
    }
    return 0;


}


PS Share Tweet +1