[BOJ] 단지번호붙이기_2667 C++ 풀이

문제

n x n 크기의 정사각형 지도에서 집이 있는 곳은 1, 없는 곳은 0으로 나타내며 상하좌우로 집이 연달아 붙어 있을경우 $($대각선은 제외)하나의 단지로 친다. 총 단지가 몇개인지와 각 단지속에 속하는 집의 수를 오름차순으로 출력하는 문제.

접근 방법

n x n배열 aptMap의 0,0 인덱스 부터 이동 하여 ‘1’을 만났을때 깊이 우선 탐색을 실행 하였다.

해당 위치의 상하좌우에 ‘1’이 존재하는지 확인하기 위해서 구조체를 사용하여 상하좌우를 구현하였다.

만약 이동한 위치 $($’1’이 존재하는 위치)의 상하좌우에 ‘1’이 존재하고 그 ‘1’이 존재하는 위치에 방문한 적이 없다면 $($aptMap[?][?]==’1’ && visited[?][?]==0) 해당 단지의 집의 수를 하나 늘리고 해당위치로 이동한 다음 깊이 우선 탐색을 반복한다.

단지들 각각의 집 개수를 저장하는 배열을 선언하고 하나의 연결 요소의 탐색이 끝났을때 집의 수 카운트를 배열에 저장하고 카운트를 다시 0으로 초기화 시켜줬다. 단지의 수는 해당 배열의 크기를 출력하는 것과 같고, 각 단지내의 집의 수는 배열의 각 인덱스에 저장된 값과 같으므로 배열을 sort 함수로 오름차순 정렬 시켜준 뒤 출력하였다.

구현

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef struct
{
    int x,y;
} d;

d dir[4]={ {-1,0}, {0,-1}, {1,0}, {0,1} }; // 동남서북
int visited[25][25]={0,};
string aptMap[25];
vector<int> result; //단지 수
int n, cnt;

void dfs(int i, int j)
{
    int newX, newY;
    visited[i][j]=1;
    cnt++;
    for(int k=0; k<4; k++)
    {
        newX = i + dir[k].x;
        newY = j + dir[k].y;

        if(newX>=0 && newX<n && newY>=0 && newY<n)
            if(aptMap[newX][newY]=='1' && visited[newX][newY]==0) dfs(newX, newY);
    }
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin>>n;
    for(int i=0; i<n; i++) cin>>aptMap[i];

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(aptMap[i][j]=='1' && visited[i][j]==0)
            {
                cnt=0;
                dfs(i,j);
                result.push_back(cnt);
            }
        }
    }
    
    sort(result.begin(), result.end());
    int len=result.size();
    cout<<len<<'\n';
    for(int i=0; i<len; i++) cout<<result[i]<<'\n';
    return 0;
}

BOJ_단지번호붙이기