백준_2667 : 단지 번호 붙이기 - C++

문제

---

문제 해석

- 입력으로 1과 0이 2차원으로 들어 온다.

- 받은 입력에서 서로 붙어 있는 1을 하나의 단지라고 본다.

- 이때 단지의 개수와 해당 단지에 1이 몇개 있는지 세어서 출력 하면 되는 문제이다.

---

알고리즘

- 그래프와 dfs 를 사용 하면 된다.

- 방문한 집을 표시하기 위한 visit 배열과 집의 위치를 담은 home 배열을 만든 후 집의 위치를 입력 받는다.

- home 배열을 탐색 하다 집이 있는 위치에서 부터 해당 집과 연결된 모든 집은 탐색하며 단지의 수를 세어 준다.

  - 방법은 다른 그래프 탐색 방법과 동일하게 진행 해 주면 된다.

  - 자세한 방법은 코드에서 설명 하도록 하겠다.

- 세어준 단지 수는 vector 에 저장 해 주고 이후에 벡터의 size 와 정렬된 벡터를 출력 해 주면 된다.

---

코드

- 그래프를 탐색 하는 대표적인 방법은 다음과 같다.

- int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; 처럼 dx와 dy 를 정해 준다.

- i 를 0~3 까지 증가 시키면서 x+dx[i], y+dy[i] 를 해주면 (x, y) 를 기준으로 상하좌우를 모두 탐색 할 수 있게 된다.

- 이때 이동한 위치가 방분 하지 않았고 집이 존재 한다면 같은 단지중 하나라고 볼 수 있기에 cnt 를 하나 증가 시켜 준다.

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

int visit[32][32];
int home[32][32];
int cnt;
vector<int> cnthome;

int N;

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

void ans(int x, int y){
    visit[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx >= N || nx < 0 || ny >= N || ny < 0) continue;
        if(visit[nx][ny] == 0 && home[nx][ny] == 1){
            cnt += 1;
            ans(x+dx[i], y+dy[i]);
        }
    }
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        string tmp;
        cin >> tmp;
        for(int j = 0; j < N; j++){
            home[i][j] = tmp[j]-'0';
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(visit[i][j] == 0 && home[i][j] == 1){
                cnt = 1;
                ans(i, j);
                cnthome.push_back(cnt);
            }
        }
    }
    sort(cnthome.begin(), cnthome.end());
    cout << cnthome.size() << '\n';
    for(int i = 0; i < cnthome.size(); i++){
        cout << cnthome[i] << '\n';
    }
}