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

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

• 코드

#include<iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <deque>
#include <bitset>

using namespace std;

int n;
vector <int> graph[900];
bool visited[25][25];
vector <int> home;
int arr[25][25] = { 0, };
int homecnt = 0;
int complexnum = 0;

void dfs(int i,int j) {
    visited[i][j] = true;
  
    homecnt++;
    if (j-1>=0 && arr[i][j - 1] == 1 && !visited[i][j - 1]) {
        dfs(i, j - 1);
        
    }
    if (j+1<n && arr[i][j + 1] == 1 && !visited[i][j + 1]) {
        dfs(i, j + 1);
        
    }
    if (i - 1 >= 0 && arr[i - 1][j] == 1 && !visited[i - 1][j]) {
        dfs(i - 1, j);
        
    }
    if (i + 1 < n && arr[i + 1][j] == 1 && !visited[i + 1][j]) {
        dfs(i + 1, j);
        
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    cin.ignore();
    for (int i = 0; i < n; i++) {
        string s;
        getline(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] == 1 && visited[i][j] == false) {
                dfs(i, j);
             
                complexnum++;
                home.push_back(homecnt);
                homecnt = 0;
            }
        }
    }
    cout << complexnum << endl;
    sort(home.begin(), home.end());
    for (int i = 0; i < home.size(); i++) {
        cout << home[i] << endl;
    }
 
}

• 알고리즘 분류 : DFS
• 문제 해설

깊이우선 탐색과 넓이우선 탐색 모두 적용 가능한 문제였다. 방문하지 않은 집이면서 1일때 dfs를 진행하고 단지 수(노드수)와 단지 개수( dfs를 진행한 횟수를)를 저장하여 출력하면 된다. 좌, 우 , 위, 아래를 모두 탐색하여야하는데 습관적으로 else if를 써서 조금 헤맸던 문제이다.