[BOJ] 2667번 : 단지번호붙이기 (C언어)

1. 문제

2667번: 단지번호붙이기

• 정사각형 지도
• 1 : 집이 있는 곳
• 0 : 집이 없는 곳
• 인접한 집끼리 단지 구성
• 인접 : 상하좌우
• 단지수 출력 후, 각 단지에 속하는 집 수를 오름차순으로 출력

2. 알고리즘

• DFS 탐색으로 단지 구성
• 단지에서 집마다 count + 1
• 오름차순은 계수정렬로 구현

3. 소스코드

#include <stdio.h>

int graph[26][26] = {0};
int apart[26*26] = {0};
int n, count, sum = 0;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= n) {
        return 0;
    }
    
    if(graph[x][y] == 1) {
        graph[x][y] = 0;
        count++;
        
        for(int i = 0; i < 4; i++) {
            dfs(x + dx[i], y + dy[i]);
        }
        return 1;
        
    }
    return 0;
    
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%1d", graph[i] + j);
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(dfs(i, j) == 1) {
                apart[count]++;
                count = 0;
                sum++;
            }
        }
    }
    
    printf("%d\n", sum);
    for(int i = 0; i < 26*26; i++) {
        if(apart[i] != 0){
            int k = apart[i];
            for(int j = 0; j < k; j++) {
                printf("%d\n", i);
            }
        }
    }
    
    return 0;
}

4. C언어

공백없는 여러개의 숫자 입력받기

문제를 보면 위와 같이 공백이 없는 숫자가 입력된다. 이 경우 scanf("%1d", )를 통해서 1개의 숫자만 입력받도록 할 수 있다. 그래서 반복문을 통해서 모든 숫자를 입력받을 수 있다.