[백준] 단지번호 붙이기_2667

처음으로 혼자서 제대로 풀어본 dfs 문제...!  

 

* 실수했던 것 * 

1. 입력 

7

0110100

0110101

1110101

...

입력이 이런 형태였는데 그냥 평소처럼 int 형태로 받다가 아예 배열에 값이 저장이 안됐었다. 

 

3. sort 함수를 잘못 사용했다. num의 크기만큼만 정렬시키면 되는데 배열 전체를 오름차순으로 정렬시켰더니 앞에는 0만 들어갈 수 밖에 없었다. 

 

2.  return 0;을 빼먹어서 런타임 오류남. 앞으로는 미리 입력하는게 좋을 것 같다. 

 

3. adj 배열의 크기를 너무 작게 잡아서 런타임 오류가 남. 앞으로는 예제만 생각하지 말고 크게크게 잡자!

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
 
int n;  
int house[25][25];
int visited[25][25];
queue<pair<int, int>> t;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int adj[625];
int num = 0;
bool isout(int ny, int nx) { return ny < 0 || nx < 0 || ny >= n || nx >= n; }
 
void dfs(int i, int j) {
    visited[i][j] = 1;
    adj[num] += 1;
    for (int d = 0; d < 4; d++) {
        int ny = i + dy[d];
        int nx = j + dx[d];
        if (isout(ny, nx)) continue;
        if (house[ny][nx] && !visited[ny][nx]) {
            dfs(ny, nx);
        }
    }
 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
 
    string str;
    for (int i = 0; i < n; i++)
    {
        cin >> str;
        for (int k = 0; k < str.size(); k++)
        {
            house[i][k] = str[k] - '0';
 
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (house[i][j] && !visited[i][j]) {
                dfs(i, j);
                num++;
            }
        }
    }
    sort(adj, adj + num);
    cout << num << "\n";
    for (int i = 0; i < num; i++) {
        cout << adj[i] << "\n";
    }
    return 0;
}