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

문제 링크 - https://www.acmicpc.net/problem/2667

🌱 문제

🌱 풀이

전체 배열(지도) 좌표를 돌면서 BFS를 통해 단지의 수 및 각 단지에 속하는 집의 수를 찾았다.

• queue<pair<int,int>> q: x,y좌표를 이용한 BFS에 활용
• vector<int> v: 각 단지의 갯수를 push_back하고, 정답 출력시 오름차순하여 출력
• char arr: 지도 배열
• dx[], dy[]: 2차원 배열에서 인접한 좌표로 넘어가고자 할 때 사용하는 배열
• bool visit

과정

1. 2차원 배열에 지도 배열을 입력받는다.
2. 전체 배열을 돌면서 아직 방문 안한 좌표이고, 집이 있는곳(arr==1)좌표에서만 BFS를 실행하였다.
3. 현재 좌표를 queue에 넣고 방문체크 한다.
4. bfs에 진입한 순간 집1개가 있는거니까 cnt는 bfs문의 처음에 1로 초기화 하였다.
5. 인접한 좌표가 아직 방문안했고, 집이 있는 좌표이면 queue에 넣고, 방문체크하고, cnt 증가시킨다.(하던대로 BFS실행)
6. 배열 인덱스 범위체크는 항상 주의하자!
7. bfs하나가 끝나면 한 단지를 다 돈것이므로 cnt를 벡터에 push_back하고, 함수를 완료한다.

주의할점

• 이 문제에서 입력값에 공백이 없으므로 int형 2차원 배열로 입력받으면 정상동작하지 않는다.
• 백준 질문검색을 참고했더니 char형 배열로 입력받아야 한다고 해서 char형 2차원 배열로 선언하였다.

🌱 코드

//2667번: 단지번호붙이기

/*
지도의 크기 N
5<=N<=25

*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int n;
queue<pair<int, int>> q;
vector<int> v;
char arr[25][25];
bool visit[25][25];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};


void bfs(int x, int y){
    int cnt=1;
    
    q.push(make_pair(x,y));
    visit[x][y]=true;
    while(!q.empty()){
       int cur_x=q.front().first;
       int cur_y=q.front().second;
       q.pop();

       for(int i=0; i<4; i++){
           int nx=cur_x+dx[i];
           int ny=cur_y+dy[i];

           if(nx<0 || ny<0 || nx>=n || ny>=n) //단지 배열 범위 벗어나면 패스
            continue;

           if(visit[nx][ny]==false && arr[nx][ny]=='1'){
               visit[nx][ny]=true;
               q.push(make_pair(nx,ny));
               cnt++;
           }
       }

    }
    v.push_back(cnt);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
           cin>>arr[i][j];
        } 
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visit[i][j]==false && arr[i][j]=='1'){ //방문하지 않았고, 집이 있는 경우만 BFS 시행
                // cout<<"x: "<<i << ", y:"<<j<<"\n";
                bfs(i,j);
            }
        }
    }

    sort(v.begin(),v.end());
    cout<<v.size()<<"\n";
    for(int i=0; i<v.size(); i++){
        cout<<v[i]<<"\n";
    }
}