[Softeer/소프티어][level2] 장애물 인식 프로그램 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409&sw_prbl_sbms_sn=16804

Softeer

 

[난이도] level2
[유형] DFS

[풀이]
전형적인 DFS 문제입니다.
입력을 받을 때 %1d 와 같이 써주면 문제의 입력과 같이 붙어있는 입력에 대해서도 한자리씩 받을 수 있습니다.
블록의 크기를 저장할때는 multiset을 이용하였습니다. 따로 정렬을 해주지 않아도 set은 트리구조이기 때문에
정렬된 상태가 유지되며 저장되기 때문입니다.

 

#include <cstdio>
#include <set>
using namespace std;
int N,map[25][25],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
bool visit[25][25];
int dfs(int y,int x){
    visit[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=N||!map[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%1d",&map[i][j]);
    multiset<int> ans;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(map[i][j] && !visit[i][j]) ans.insert(dfs(i,j));
    printf("%d\n",ans.size());
    for(auto v : ans) printf("%d\n",v);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/장애물_인식_프로그램.cpp