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

 

1) 문제설명

 

백준 Online Judge 2667번 단지번호붙이기

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

2667번: 단지번호붙이기

 

2) 아이디어

 

처음 좌표는 0,0으로 잡고 가로를 X 세로를 Y로 잡았다.

배열을 순환하다가 값이 1일 경우 DFS함수를 호출하여 카운트를 하나 증가시키고 값을 0으로 초기화시킨다.

이후 다시 X의 좌표와 Y의 좌표에 각각 +1, -1 씩 더하여 DFS를 재귀적으로 호출하였다. 이때 X, Y의 좌표가 1이 아닐 경우 아무것도 하지 않고 return 하기 때문에 1이 연속적으로 붙어있는 단지만 카운트를 증가시킬 수 있다.

이런 카운트 값을 오름차순인 우선순위 큐에 넣고 출력하였다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int n;

priority_queue <int,vector<int>,greater<int>> v; // 우선순위 큐를 오름차순으로 정렬

int arr[30][30];
int cnt = 0;

void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n) { // 범위에서 벗어날 경우 return
        return;
    }
    
    if (arr[x][y] == 1) { // 1인 단지일때
        arr[x][y] = 0; // 0으로 초기화 후
        cnt++; // 갯수를 세어준다
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }
 
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) {
                dfs(i, j);
                v.push(cnt);
                cnt = 0;
            }
        }
    }
    cout << v.size() << endl;
    
    while (!v.empty()) {
        cout << v.top() << endl;
        v.pop();
    }
}