2667번 : 단지번호붙이기

dfs, bfs 모두 사용 가능한 문제 나는 dfs를 썻다. 신경써야할 부분은 2차원 배열로 되어 있는 부분에서 정해진 공간을 넘어가지 않기 위해 범위를 설정하는 것과 입력이 공백없이 되어 있어서 cin을 이용해야한다는 것! 탐색보다는 다른부분이 신경쓸게 더 많다.. 비슷한 문제는 솔직히 코드를 카피앤 페이스트하고 싶다. cin.get()은 문자를 입력으로 받아서 1은 사실 31이다 여기서 아스키코드 '0'을 빼주면 실제로 값이 1이된다. 유용한 테크닉인거 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0;
int total = 0;
int num = 1;
vector<vector<int>> a (26);
vector<int> ans;
int check[27][27];
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
 
void dfs(int r, int c)
{
    check[r][c] = num;
    ++total;
    for (int k = 0; k < 4; ++k)
    {
        int nr = dr[k] + r;
        int nc = dc[k] + c;
        if (nr >= 0 && nc >= 0 && nr < n && nc < n)
            if (check[nr][nc] == 0 && a[nr][nc] == 1)
            {
                dfs(nr, nc);
            }
    }
}
 
int main()
{    
    cin >> n;
    cin.get();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int input = cin.get() - '0';
            a[i].push_back(input);
        }
        cin.get();
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            if (a[i][j] == 1 && check[i][j] == 0)
            {
                total = 0;
                dfs(i, j);
                num++;
                ans.push_back(total);
            }
        }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << endl;
    return 0;
}