[c++/알고리즘] 백준 2667 단지번호붙이기 : DFS
// 이것역시 시작점이 없으니 dfs를 사용한다고 생각하고 풀어보자
#include <iostream>
#include <queue>
#include <functional> // greater
using namespace std;
int n, hcnt = 1;
int map[26][26];
int ch[26][26];
int dx[4] = { 0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void DFS(int x, int y){
for(int i=0; i<4; i++){
if(x+dx[i] < 0 || x+dx[i]>=n || y+dy[i] < 0 || y+dy[i] >= n) continue;
if(ch[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 1){
ch[x+dx[i]][y+dy[i]] = 1;
hcnt++;
DFS(x+dx[i], y+dy[i]);
}
}
}
int main(){
priority_queue<int, vector<int>, greater<int> > pQ;
int h, cnt=0;
cin >> n;
for(int y = 0; y< n; y++){
for(int x=0; x<n; x++){
scanf("%1d", &map[x][y]);
}
}
for(int y = 0; y< n; y++){
for(int x=0; x<n; x++){
if(ch[x][y] == 0 && map[x][y] == 1){
ch[x][y] = 1;
DFS(x, y);
cnt++;
pQ.push(hcnt);
hcnt = 1;
}
}
}
cout << cnt << endl;
while(!pQ.empty()){
cout << pQ.top() << endl;
pQ.pop();
}
return 0;
}
Author And Source
이 문제에 관하여([c++/알고리즘] 백준 2667 단지번호붙이기 : DFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myeongs07/c알고리즘-백준-2667-단지번호붙이기-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)