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

0. 제목

• 백준 2667 단지번호붙이기
• BOJ 2667 단지번호붙이기
• C++ 2667 단지번호붙이기

---

1. 문제

https://www.acmicpc.net/problem/2667

---

2. 풀이

• 미로찾기와 비슷한 문제이다.
• 먼저 dx, dy는 좌,우,상,하 순으로 움직일 수 있도록 좌표설정을 한 배열이다.
• 이 문제에서 주의할 점이 입력을 받을 때 문자열로 받아야 한다는 것이다. 문자열로 받은 후 한글자마다 숫자로 만들어주었다.
• dfs함수를 보면 탐색을 할 때마다 cnt를 1씩 증가시켜준다. 그 후 visited의 원소를 true로 바꿔주고 반복문을 실시하게 된다.
• 이 반복문은 좌,우,상,하로 탐색을 실시하게 해주며 만약 좌표가 0보다 작아지거나 N보다 같거나 커지면 즉, 범위를 벗어나게 되면 건너뛰게 된다.
• 범위 내에 있고 arr값이 1이고 visited값이 false이면 재귀적으로 dfs를 실시해준다.
• 그렇게 하면 cnt값은 증가할 것이다.
• 단지가 끝날때마다 cnt값을 vector에 넣어주고 0으로 초기화시킨다.
• main에서 2중 반복문이 모두 끝나면 vector에는 단지 수들이 원소로 들어가있다.
• vector의 size() 함수를 써서 총 단지수를 구하고 sort()를 이용하여 오름차순으로 정렬하면 된다.

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAX 25
 
int N;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,1,-1};
int cnt;
 
vector<int> cnt_vec;
 
void dfs(int x, int y){
    cnt++;
    visited[x][y] = true;
 
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if(arr[nx][ny] == 1 && visited[nx][ny] == false)
            dfs(nx, ny);
    }
}
 
 
int main(int argc, const char * argv[]) {
    string line;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> line;
        for(int j = 0; j < N; j++){
            arr[i][j] = line[j] - '0';
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(arr[i][j] == 1 && visited[i][j] == false){
                cnt = 0;
                dfs(i, j);
                cnt_vec.push_back(cnt);
            }
        }
    }
    
    sort(cnt_vec.begin(), cnt_vec.end());
    cout << cnt_vec.size() << '\n';
    for(int i = 0; i < cnt_vec.size(); i++)
        cout << cnt_vec[i] << '\n';
    
    return 0;
}