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

0. [c++] 백준

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

1. 풀이

BFS를 활용하여 문제를 풀어보았다.

하다보니 BFS가 DFS에 비해서 굳이 다른 배열을 활용할 필요가 없어서 간단하게 만들 수 있디는 것이 가장 큰 장점인 것 같다.

탐색순서가 필요하지 않은 배열이면 이를 활용하는게 편한 것 같다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include<iostream> #include<queue> #include<vector> #include<string> #include<algorithm>   using namespace std;   int N; vector<string> poorHouse; bool visited[25][25]; int Count; vector<int> countArr; int dirY[4] = { 0,0,1,-1 }; int dirX[4] = { 1,-1,0,0 };   //DFS     //BFS void BFS(int hereY, int hereX) {     if (visited[hereY][hereX])         return;     visited[hereY][hereX] = true;     Count++;     for (int i = 0; i < 4; i++) {         int thereX = hereX - dirX[i], thereY = hereY - dirY[i];         //범위를 벗어나지 않고,         if (thereX < N&& thereX >= 0 && thereY < N&&thereY >= 0)             //아직 방문하지 않았고, 그곳이 1이라면 방문하자.             if (!visited[thereY][thereX] && poorHouse[thereY][thereX] == '1') {                 //그곳을 방문한다.                 BFS(thereY, thereX);             }              } }     int main() {          //int num = 0;     cin >> N;     string temp;     for (int i = 0; i < N; i++) {         cin >> temp;         poorHouse.push_back(temp);     }       //BFS     for(int y=0;y<N;y++)         for (int x = 0; x < poorHouse[y].size(); x++) {             if (poorHouse[y][x] == '1' && !visited[y][x]) {                             Count = 0;                 BFS(y, x);                 /*cout << "x : " << x << " Y : " << y << " count : " << Count << endl;*/                 countArr.push_back(Count);             }         }         sort(countArr.begin(), countArr.end());     cout << countArr.size() << endl;     for (int i = 0; i < countArr.size(); i++) {         cout << countArr[i] << endl;     } } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!