Softeer - 장애물 인식 프로그램

softeer.ai/practice/info.do?eventIdx=1&psProblemId=409

Softeer

블록의 영역 크기를 구하기 위하여 DFS 기법을 이용

블록의 영역 크기를 오름차순으로 출력하기 위해 우선순위큐(최솟값 우선)를 사용

 

 

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int arr[25][25];
bool visited[25][25];
int N;
int total_block_num=0;
int count=0;

int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, 1, -1};

void dfs(int x, int y)
{
        if(x < 0 or y < 0) return;
        if(x >= N or y >= N) return;
        if(arr[y][x]==0) return;
        
        if(visited[y][x]) return;
        else visited[y][x]=true;

        count++;
        for(int i=0; i<4; i++)
        {
                int nx=x+dx[i];
                int ny=y+dy[i];
                dfs(nx,ny);
        }
}

int main(int argc, char** argv)
{
       cin >> N;

        for(int i = 0; i < N; i++)
        {
                string values;
                cin >> values;

                for(int j = 0; j < N; j++)
                {
                        arr[i][j] = values[j]-48;
                        visited[i][j]=false;
                } 
        }

        priority_queue<int, vector<int>, greater<int>> q;
        for(int i = 0; i < N; i++)
        {
                for(int j = 0; j < N; j++)
                {
                        if(arr[i][j] and not visited[i][j])
                        {
                                total_block_num += 1;
                                count=0;
                                dfs(j, i);
                                q.push(count);
                        }
                }
        }
        cout << total_block_num << '\n';
        while (!q.empty()) {
                cout << q.top() << '\n';
                q.pop();
        }

         return 0;
}