[BOJ] #2667 단지번호붙이기

시간 제한	메모리 제한	정답 비율
1 초	128 MB	38.045 %

 

2667번: 단지번호붙이기

동서남북 네 방향으로 연결된 집들의 모임을 단지라고 한다. 단지에 해당하는 집의 수를 오름차순으로 정렬하여 출력하는 문제이다.

입력이 띄어쓰기 없이 문자열로 주어져 string으로 받아 int배열에 넣어주었다.
이중 포문을 도는데 해당 위치에 집이 있으면 하나의 단지로 간주하고 dfs를 돌아 단지 내의 집의 수를 구한다. 이 때 chk 배열을 이용하여 중복을 방지한다. 

포문이 끝나면 모든 단지를 탐색한 것이므로 저장해놨던 단지 내의 집의 수를 정렬하여 출력한다.

 

메모리	시간
1996 KB	0 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
using namespace std;
 
int di[] = { 0,0,1,-1 };
int dj[] = { 1,-1,0,0 };
int n, cnt;
int arr[26][26];
int chk[26][26];
vector<int> v;
 
void dfs(int r, int c) {
    cnt++;
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nextr = r + di[i];
        int nextc = c + dj[i];
        if (nextr >= 0 && nextr < n && nextc >= 0 && nextc < n) {
            if (arr[nextr][nextc] && !chk[nextr][nextc]) {
                dfs(nextr, nextc);
            }
        }
    }
}
 
int main() {
    scanf("%d", &n);
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < s.length(); j++) {
            arr[i][j] = s[j] - '0';
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] && !chk[i][j]) {
                dfs(i, j);
                v.push_back(cnt);
                cnt = 0;
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", v.size());
    for (int i = 0; i < v.size(); i++) {
        printf("%d\n", v[i]);
    }
 
    return 0;
}