백준 2667 - 단지 번호 붙이기

연결된 단지가 몇 개인지, 각 단지의 집이 몇 개인지 출력하는 문제

dx와 dy로 4방향을 정함 (상, 하, 좌, 우)

for문으로 방문하지 않은 모든 집에서 dfs 함수를 실행함 (연결되지 않은 집은 dfs로 방문할 수 없기 때문에)

dfs함수 안에서 상,하,좌,우 4 방향으로 연결된 집을 찾고 연결되어 있으면서 방문하지 않았다면 dfs

각각의 단지들의 집의 개수를 cnt로 구한 후 answer 벡터에 각각 저장

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

bool arr[26][26] = { false }; //방문 여부 확인 배열
int n[26][26];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int N;
int cnt = 0;

void DFS(int x,int y) { //시작할 위치
    cnt++;

    arr[x][y] = true;

    for (int i = 0; i < 4; i++) { //상하좌우
        int nx = x+dx[i];
        int ny = y+dy[i];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (!arr[nx][ny] && n[nx][ny] == 1) { //방문하지 않았고 집이 있을 때
            DFS(nx, ny);
        }
        
    }

}



int main() {

    int i,j;
    int u, v;
    char s[26];

    vector<int> answer;
    
    scanf("%d", &N);


    for (i = 0; i < N; i++) {
        scanf("%s", s);
        for (j = 0; j < N; j++) {
            n[i][j] = s[j] - '0';
        }
    }


    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (!arr[i][j] && n[i][j] == 1) { //방문한 적 없고 집이 있을 때만
                cnt = 0;
                DFS(i, j);
                answer.push_back(cnt);
            }
        }
    }

    sort(answer.begin(), answer.end());

    printf("%d\n", answer.size());

    for (i = 0; i < answer.size(); i++) {
        printf("%d\n", answer[i]);
    }

    return 0;
}