백준 2667 단지번호붙이기

그래프를 위한 vector 배열을 만들 필요가 없다.

효율적으로 풀기 위해서 visit 배열을 bool이 아니라 int 형으로 선언해서 문제에 나온 그림과 같이 번호를 넣어준다.

4방향을 check하는 것이 중요하다.

 

sort할 때 정렬할 index를 잘 설정하자.

자세한 설명은 주석으로..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int n;
int ar[25][25];
int visit[25][25];
int ans[25 * 25];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
void dfs(int row, int col, int last) {
    visit[row][col] = last;
 
    //4방향으로 check를 한다.
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        //배열 안에 들어오는지 검사
        if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
            //방문한 곳인지 검사
            if (visit[nr][nc] == 0 && ar[nr][nc] == 1) {
                dfs(nr, nc, last);
            }
        }
    }
}
 
int main(int argc, char** argv) {
    int last = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //%1d는 붙어 있는 숫자들을 한 개씩 인식하여 입력받는다.
            scanf("%1d", &ar[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (visit[i][j] == 0 && ar[i][j] == 1) {
                dfs(i, j, ++last);
            }
        }
    }
 
    printf("%d\n", last);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[visit[i][j]]++;
        }
    }
    //1번 부터 last번 까지 ans에 넣었으므로, 정렬을 그 index에 맞춰서 해준다.
    sort(ans + 1, ans + last + 1);
    for (int i = 1; i <= last; i++) printf("%d\n", ans[i]);
 
    return 0;
}