[백준] 2667번: 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제 이해

모든 경우를 탐색해서, 연결되어 있는 것들의 수를 세서 저장하면 된다. (map[i][j] == 0일때 BFS 혹은 DFS를 돌리기)

모든 경우를 탐색하기 때문에 DFS를 이용해도 되고, BFS를 이용해도 된다.

문제를 잘 읽어야하는게, 집의 개수를 저장한 배열을 정렬해서 출력해야 한다. (안했다가 계속 허탕침)

 

작성 코드(C)

1. BFS 이용

#include <stdio.h>
#include <stdlib.h>

int N;
int map[25 + 5][25 + 5];
int danji;
int house[25 * 25];

// 방향 벡터
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };

// 큐
typedef struct pos {
    int y;
    int x;
}POS;

POS q[25 * 25 + 10];
int wp, rp;

void enq(int y, int x) {
    q[wp].y = y;
    q[wp].x = x;
    wp++;
}

POS deq(void) {
    POS tmp = q[rp];
    rp++;
    return tmp;
}

int empty(void) {
    return wp == rp;
}

void BFS(int y, int x) {

    wp = 0, rp = 0;
    int cnt = 1;
    map[y][x] = 0;
    enq(y, x);

    while (!empty()) {
        POS cur = deq();
        for (int i = 0; i < 4; i++) {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            if (ny < 0 || ny >= N) continue;
            if (nx < 0 || nx >= N) continue;
            if (map[ny][nx] != 1) continue;

            map[ny][nx] = 0;
            enq(ny, nx);
            cnt++;
        }
    }
    house[danji] = cnt;
    danji++;
}

int comp(const void* a, const void* b) {

    int* p = (int*)a;
    int* q = (int*)b;
    return *p - *q;
}

int main(void) {

    // 입력받기
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1d", &map[i][j]);
        }
    }

    // BFS
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1) BFS(i, j);
        }
    }

    // output
    qsort(house, danji, sizeof(house[0]), comp);

    printf("%d\n", danji);
    for (int i = 0; i < danji; i++) {
        printf("%d\n", house[i]);
    }
    return 0;
}

 

2. DFS 이용

#include <stdio.h>

int N;
int map[25 + 5][25 + 5];

int cnt;
int ans_cnt = 0;
int ans[25 * 25 + 10];

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

void dfs(int y, int x) {

    if (map[y][x] == 0) return;

    map[y][x] = 0;
    cnt++;

    for (int i = 0; i < 4; i++) {

        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
        dfs(ny, nx);
    }

}

int sort() {
    for (int i = 0; i < ans_cnt; i++) {
        for (int j = i+1; j < ans_cnt; j++) {
            if (ans[i] > ans[j]) {
                int t = ans[i];
                ans[i] = ans[j];
                ans[j] = t;
            }
        }
    }
}

int main(void) {

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%1d", &map[i][j]);
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1) {
                dfs(i, j);
                ans[ans_cnt] = cnt;
                ans_cnt++;
                cnt = 0;
            }
        }
    }

    sort();
    printf("%d\n", ans_cnt);
    for (int i = 0; i < ans_cnt; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}