백준 2667 - 단지번호붙이기

문제설명

 

 

=> dfs를 적용하여 풀면 되는 문제입니다. 

• 인접한 곳을 확인할 수 있는 행렬을 생성합니다. 
• 해당 행렬을 통해 현재 확인하고 있는 정점의 주위 행렬을 확인합니다. 
• 주위를 확인해갈때 범위가 넘어가지 않았는지 확인합니다. 
• 더 이상 확인할 곳이 없을 때, 하나의 단지가 끝납니다. 
• 이러한 방식으로 모든 구역에 있는 집들을 확인합니다. 

 

<code>

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N;
int Map[26][26]={0};
bool Visited[26][26]={false};
vector<int> NoHome;
int cnt;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};

void dfs(int x, int y)
{
    cnt++;
    Visited[x][y] = true;
    for(int i=0; i<4; i++)
    {
        int goingX = x +dx[i];
        int goingY = y +dy[i];
        
        if(goingX < 0 || goingX >= N || goingY <0 || goingY >=N)continue;
        if(Map[goingX][goingY] != 0 && Visited[goingX][goingY] == false)//탐색 가능
        {
            dfs(goingX, goingY);
        }
    }
}

int main()
{
   // ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
   
    scanf("%d", &N);
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%1d", &Map[i][j]);
        }
    }
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(Map[i][j] == 1 && Visited[i][j] == false)//집이 있고 가보지 않은 집인 경우
            {
                cnt =0;
                dfs(i,j);
                NoHome.push_back(cnt);//집 갯수 추가하기
            }
        }
    }
    
    sort(NoHome.begin(), NoHome.end());
    int limit = NoHome.size();
    cout << limit<<'\n';
    
    for(int i=0; i<limit; i++)
    {
        cout<<NoHome[i]<<'\n';
    }
    
    return 0;
}

 

 

 

실행 화면

 

 

---

주의 사항 : ios_base::sync_with_stdio(false) 를 한 이후에는 cin과 scanf를 섞어 쓰면 안 됩니다.