[C++] BOJ 2667번 : 단지번호붙이기

📝 문제

---

💻 실행 코드

// BOJ 2667번 : 단지번호붙이기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = {0, 1, 0, -1}; // 상 우 하 좌
int dy[4] = {-1, 0, 1, 0};
int n;
int map[26][26];
int house;
vector<int> v;

void DFS(int i, int j);

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%1d", &map[i][j]); // 숫자 하나씩 입력받기 위해 scnaf 사용
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(map[i][j] == 1){ // 만약 집이 있다면
                house = 0; // 집 0으로 초기화
                DFS(i, j);
                v.push_back(house); // house push
            }
        }
    }
    sort(v.begin(), v.end()); // 벡터 정렬
    cout << v.size() << "\n"; // 단지의 개수 출력
    for(int i = 0; i < v.size(); i++) // 벡터 원소 출력 (단지의 집 개수)
        cout << v[i] << "\n";
}

void DFS(int i, int j){
    map[i][j] = 0; // map[i][j] 0으로 설정
    house++; // 집 수 증가
    for(int k = 0; k < 4; k++){ // 상하좌우
        if(i + dy[k] < 0 || i + dy[k] >= n || j + dx[k] < 0 || j + dx[k] >= n)
            continue; // 만약 집이 없다면 continue
        if(map[i + dy[k]][j + dx[k]] == 1) // 상하좌우 중 집이 있다면
            DFS(i + dy[k], j + dx[k]); // 재귀 호출 (그 집을 매개변수로)
    }
}

---

📚 문제 풀이

• DFS로 문제 해결
• 먼저 숫자를 하나씩 입력받아 배열에 저장하기 위해 scanf를 사용
• 만약 map[i][j]가 1이라면 집이라는 뜻으로 house 변수를 0으로 초기화하고 DFS 함수를 호출. 그 이후 DFS 함수가 끝난 이후의 house 변수를 벡터에 push
• DFS 함수에서는 map[i][j]의 상하좌우를 살피고 값이 1이라면 house 변수 증가시키고 재귀 호출해 다시 탐색
• 탐색이 끝났다면 벡터를 정렬하고, 벡터 원소 개수와 원소를 오름차순으로 출력

---

✅ 실행결과