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

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

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

이 문제는 그래프 문제의 일종으로, 아파트 단지처럼 1이 연속되어있는 부분이 몇개인지와, 몇개의 1들로 이루어져있는지 구하는 문제 입니다.

각 요소가 몇개의 요소로 이루어져있는지는 BFS or DFS를 이용하여 전부 순회하면서 카운팅 하면 되고, 그리고 연속되어있는 부분 덩이가 몇개인지는 맵을 하나하나 돌면서 방문 안한 지점이 나올때마다 1개씩 올려주면 되겠습니다.

소스코드 : 

#include 
#include 
#include 
#include 
using namespace std;


int N;
bool visited[27][27];
vector< vector > v(27, vector(27, 0));

// 동서남북 방향으로 1칸씩 가기 위한 move 세팅
struct move {
 int y, x;
}move[4] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } };

// 몇개 원소이며, 각 요소가 몇개 필요한지 저장할 벡터
vector counter;
int cnt = 0;

// DFS를 이용하여 갈수있는 모든곳을 가본다.
void DFS(int y, int x) {
 visited[y][x] = true;
 for (int t = 0; t < 4; t++) {
  if (v[y + (::move[t].y)][x + (::move[t].x)] == 1 && visited[y + (::move[t].y)][x + (::move[t].x)] == false) {
   visited[y + (::move[t].y)][x + (::move[t].x)] = true;
   cnt++;
            DFS(y+::move[t].y , x +::move[t].x);
  }
 }
}


int main() {
 cin >> N;
    for (int i = 1; i <= N; i++) {
  for (int j = 1; j <= N; j++) {
   scanf("%1d", &v[j][i]);
  }
 }

 for (int i = 1; i <= N; i++) {
  for (int j = 1; j <= N; j++) {
            // 이번 장소가 한번도 안가봤는데 갈수 있는 길이면,
   if (visited[j][i] == false && v[j][i] == 1) {
    cnt++;
    DFS(j, i);
    counter.push_back(cnt);
    cnt = 0;
   }
   
  }
 }
    // 오름차순으로 정렬 후 출력
 sort(counter.begin(), counter.end());
 int size = counter.size();
 cout << size << endl;
 for (int i = 0; i < size; i++) {
  cout << counter[i] << endl;
 }

}