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

문제는 다음과 같습니다.

문제 풀이는 다음과 같습니다.
입력받은 2차원 배열에 시작부터 끝까지 방문하지 않은 지점에 대해서 dfs를 수행하고,
❗️이때에 dfs는 각 배열 위치에서 상, 하, 좌, 우에 대해 수행하면 됩니다.❗️

그리고 저는, 배열의 범위를 초과하는지 신경쓰기 싫어서
애초에 테두리를 설정하고,
입력을 인덱스 1부터 받고 전체 배열의 범위를 +2씩 더해주었습니다.

그리고 전체 단지 수는 변수 cnt에 담았고,
한 단지에 있는 집의 수는 변수 tmp에 담았습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int a[28][28]={0, };
int ch[28][28]={0, }; // 중복체크
vector<int> res;
int tmp;

void DFS(int u, int v){
  ch[u][v]=1;
  tmp++;
  // 상,하,좌,우에 대해서 dfs수행
  if(ch[u][v-1]==0 && a[u][v-1]==1) DFS(u, v-1);
  if(ch[u][v+1]==0 && a[u][v+1]==1) DFS(u, v+1);
  if(ch[u-1][v]==0 && a[u-1][v]==1) DFS(u-1, v);
  if(ch[u+1][v]==0 && a[u+1][v]==1) DFS(u+1, v);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin>>n;
    for(int i=1; i<=n; i++){
      string s;
      cin>>s;
      for(int j=0; j<s.size(); j++){
        if(s[j]=='0') a[i][j+1]=0;
        else a[i][j+1]=1;
      }
    }
    int cnt=0;
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        tmp=0; // 집의 개수
        if(ch[i][j]==0 && a[i][j]==1){
          DFS(i, j);
          cnt++; // 총 단지 수
        }
        if(tmp) res.push_back(tmp);
      }
    }
    sort(res.begin(), res.end());
    cout<<cnt<<"\n";
    for(int i=0; i<res.size(); i++){
      cout<<res[i]<<"\n";
    }
    return 0;
}

2/16 수요일 복습)

• dfs이용

#include <bits/stdc++.h>
 using namespace std;

 int v[27][27]={0, };
 int ch[27][27]={0, };
 vector<int> a;
 int n, m, tmp;

 void DFS(int a, int b){
   tmp++;

   if(v[a+1][b]==1 && ch[a+1][b]==0){
     ch[a+1][b]=1; DFS(a+1, b);
   }
   if(v[a][b+1]==1 && ch[a][b+1]==0){
     ch[a][b+1]=1; DFS(a, b+1);
   }
   if(v[a-1][b]==1 && ch[a-1][b]==0){
     ch[a-1][b]=1; DFS(a-1, b);
   }
   if(v[a][b-1]==1 && ch[a][b-1]==0){
     ch[a][b-1]=1; DFS(a, b-1);
   }
 }

 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     cin>>n;
     for(int i=1; i<=n; i++){
       string str; cin>>str;
       for(int j=0; j<str.size(); j++){
         if(str[j]=='0') v[i][j+1]=0;
         else v[i][j+1]=1;
       }
     }

     int res=0;
     // DFS수행
     for(int i=1; i<=n; i++){
       for(int j=1; j<=n; j++){
         tmp=0;
         if(ch[i][j]==0 && v[i][j]==1){
           ch[i][j]=1;
           DFS(i, j);
           res++;
           a.push_back(tmp);
         }
       }
     }

     cout<<res<<endl;
     sort(a.begin(), a.end());
     for(int i=0; i<a.size(); i++) cout<<a[i]<<"\n";
     return 0;
 }

• bfs 이용

#include <bits/stdc++.h>
 using namespace std;

 int v[27][27]={0, };
 int ch[27][27]={0, };
 vector<int> a;
 int n, tmp;

 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     int v[27][27]={0, };
     int ch[27][27]={0, };
     vector<int> a;
     int n, tmp, res=0; cin>>n;

     for(int i=1; i<=n; i++){
       string str; cin>>str;
       for(int j=0; j<str.size(); j++){
         if(str[j]=='0') v[i][j+1]=0;
         else v[i][j+1]=1;
       }
     }

     // BFS수행
     for(int i=1; i<=n; i++){
       for(int j=1; j<=n; j++){
         if(ch[i][j]==0 && v[i][j]==1){
           tmp=0; res++;
           queue<pair<int, int>> q;
           ch[i][j]=1; q.push({i, j});

           while(!q.empty()){
             pair<int, int> p;
             p = q.front(); q.pop();
             tmp++;
             
             int a = p.first; int b = p.second;

             if(v[a+1][b]==1 && ch[a+1][b]==0){
               ch[a+1][b]=1; q.push({a+1, b});
             }
             if(v[a][b+1]==1 && ch[a][b+1]==0){
               ch[a][b+1]=1; q.push({a, b+1});
             }
             if(v[a-1][b]==1 && ch[a-1][b]==0){
               ch[a-1][b]=1; q.push({a-1, b});
             }
             if(v[a][b-1]==1 && ch[a][b-1]==0){
               ch[a][b-1]=1; q.push({a, b-1});
             }
           } // while문 끝(BFS 끝)
           a.push_back(tmp);
         } // if문 끝
       }
     }

     cout<<res<<endl;
     sort(a.begin(), a.end());
     for(int i=0; i<a.size(); i++) cout<<a[i]<<"\n";
     return 0;
 }