[Baekjoon] 백준 2667번: 단지번호붙이기 (c++)

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

2667번: 단지번호붙이기

 

DFS 정석 문제같은 느낌이었다.

1. 지도에서 1인곳을 방문하여, 이어진 칸 개수만큼 개수를 세고, 벡터에 개수를 저장한다.

2. 이어져있지 않은 곳은 또 따로 칸 개수를 세고 칸 개수를 저장해서,

3. 마지막에 벡터를 오름차순으로 정렬한 뒤 , 크기와 함께 요소들을 순서대로 출력해주면 된다.

 

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 26

int px[4] = { 0, 0, -1, 1 }; //상 하 좌 우
int py[4] = { -1, 1, 0, 0 };
int map[MAX][MAX] = {0};
bool isVisited[MAX][MAX] = {false,};
int Max, cnt;

void DFS(int x, int y, int N){
   
    if(isVisited[y][x]) return;
    isVisited[y][x] = true;
    cnt++;
    Max = max(Max, cnt);
    
    for(int i=0;i<4;i++){
        int dx = x + px[i];
        int dy = y + py[i];
        
        if(dx < 0 || dx >= N || dy < 0 || dy >= N || map[dy][dx] == 0 || isVisited[dy][dx]) continue;
        
        DFS(dx, dy, N);
        
    }
    
}

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int N;
    vector<int> num;
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) scanf("%1d", &map[i][j]);
    }
   
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] == 1 && !isVisited[i][j]) {
                cnt = 0;
                Max = 0;
                DFS(j, i, N);
                num.push_back(Max);
            }
        }
    }
    
    sort(num.begin(), num.end());
    
    cout << num.size() << "\n";
    for(int i=0;i<num.size();i++) cout << num[i] << "\n";
    
    
    return 0;
}