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

문제

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

풀이과정

DFS로 이차원 배열을 모두 탐색하며 끊기는 부분마다 단지번호를 주면 된다.
앞에서 풀었던 DFS를 이용해 이분 그래프의 개수를 출력하는 문제와 비슷하게 풀면 될 것 같아서 그렇게 풀어봤다. 이런 문제는 DFS,BFS 구현에 대해 아무런 지식이 없을 때 절대 못 풀었었는데 이제는 조금 감이 오는 것 같아서 좋다.

소스코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> a[26];
int visited[26][26];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int n;
int ans[25 * 25]; // n 최대값이 25 , 단지번호의 최대수 : 25*25

void dfs(int cnt,int x,int y)
{
    visited[x][y] = cnt;

    for (int k = 0; k < 4; k++)
    {
        int nx = dx[k] + x; int ny = dy[k] + y;
        if (0 <= nx && nx < n && 0 <= ny && ny < n)
        {
            if (a[nx][ny] == 1 && visited[nx][ny] == 0 )
            {
                dfs(cnt,nx, ny);
            }
        }
    }
}

int main()
{
    string str;

    cin >> n;

    cin.ignore();

    for (int i = 0; i < n; i++)
    {
        getline(cin, str);
        for (int j = 0; j < n; j++)
        {
            a[i].push_back(str[j]-48);
        }
    }

    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == 1 && visited[i][j] == 0)
            {
                dfs(++cnt, i, j);
            }
        }
    }

    cout << cnt << "\n";

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            ans[visited[i][j]] += 1;
        }
    }

    sort(ans + 1, ans + cnt + 1);

    for (int i = 1; i <= cnt; i++)
        cout << ans[i] << "\n";

    return 0;
}