[백준 2667] 단지번호 붙이기

• 1은 집이고, 0은 집이 없는 곳
  

• 영역 구별하기 문제
• 단지(영역)의 갯수를 구하고, 단지의 크기를 오름차순으로 정렬 후 출력
• DFS를 사용하여 탐색 가능

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#define MAX 25

using namespace std;

int n;

int a[MAX + 1][MAX + 1]; //집 정보

bool visited[MAX + 1][MAX + 1]; //방문 정보

vector<int> ans;

vector<string> map; 

//좌표의 방향 설정 (상, 하, 좌, 우)

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

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

int main() {

//입력받고

   //전체 map을 순환하면서 집인 경우인데 방문하지 않은 집( 1 && visited[i][j] = false) 탐색

   //go(i, j) 함수를 사용해서 단지 내의 집의 갯수를 카운트한다.

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (a[i][j] == 1 && visited[i][j] == false) {

visited[i][j] = true;

int cnt = go(i, j);

ans.push_back(cnt); //갯수들을 벡터를 이용하여 저장

}

}

}

         //정렬 후 출력!

cout << ans.size() << endl;

sort(ans.begin(), ans.end());

for (int i = 0; i < ans.size(); i++) {

cout << ans[i] << endl;

}

return 0;

}

int go(int x, int y) {

int ret = 0;

 //현재 위치에서 상, 하, 좌, 우로 좌표를 이동

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; //밖의로 나갈 경우 

if (a[nx][ny] == 0) continue; //집이 아닌 경우

//집인 경우 방문했다고 기록하고 DFS 실행하기

if (visited[nx][ny] == false) {

visited[nx][ny] = true;

ret += go(nx, ny);

}

}

  //현재 자신의 집 갯수(1) 와 연결된 집들의 갯수(ret) 의 합을 리턴해준다.

return 1 + ret;

}

---

Review.

전형적인 DFS 문제이고 , 단지별 영역을 구별하기 위해 방문정보를 잘 갱신해주는 것이 포인트였던 문제.