2667번 - 단지번호붙이기(c++)

🗒 2667번 문제

📌 DFS를 사용해서 구현한 문제(유기농배추와 유사) ❗️

🥬 유기농 배추 보러가기

1️⃣ 위, 아래, 왼쪽, 오른쪽을 돌면서 옆집이 있는 지 확인하기
-> dx, dy 배열을 사용해서 4방향 탐색을 하자

2️⃣ 인접한 옆집이 있다면 단지 내 집 수(cnt)를 올리기

3️⃣ dfs로 구현했기에 해당 노드에서 인접한 옆집이 없을 때까지 옆집 찾기
-> 없으면 그 다음 단지 찾기

4️⃣ scanf로 map상의 0,1를 받아온다 -> "%1d"로 받으면 01010이 와도 0, 1, 0, 1, 0이 따로 들어감

5️⃣ 집을 하나 찾으면 일단 찾은 단지 수를 늘리고 dfs로 옆집을 찾아다님

6️⃣ 각 단지마다의 집 수는 cnts 배열 안에 넣어둔다

7️⃣ 오름차순으로 정렬해서 print해야 하기에 sort함수를 사용해서 정렬

➰ 코드로 나타낸 2667번 ➰

#include <iostream>
#include <algorithm>

using namespace std;

int sizes, cnt = 0;
int totalDanJi = 0;
int map[25][25] = { 0 };
int cnts[625] = { 0 };

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

void dfs(int x, int y) {
    if (map[x][y] == 1) {
        map[x][y] = 0;
        cnt++;
        
        for (int i = 0; i < 4; i++) {
            int qx = x + dx[i];
            int qy = y + dy[i];
            
            if (qx >= 0 && qx < sizes && qy >= 0 && qy < sizes) {
                dfs(qx, qy);
            }
        }
    }
}

int main() {
    int index = 0;
    
    cin >> sizes;
    
    for (int i = 0; i < sizes; i++) {
        for (int j = 0; j < sizes; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    for (int i = 0; i < sizes; i++) {
        for (int j = 0; j < sizes; j++) {
            if (map[i][j] == 1) {
                totalDanJi++;
                dfs(i, j);
                cnts[index++] = cnt;
                cnt = 0;
            }
        }
    }
    
    printf("%d\n", totalDanJi);
    
    sort(cnts, cnts+totalDanJi);
    
    for (int i = 0; i < totalDanJi; i++) {
        printf("%d\n", cnts[i]);
    }
}