[2667번] 단지번호붙이기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

BFS를 통해 문제를 해결할 수 있다.

모든 좌표를 돌며 이미 방문한 점이면 return을 해주고 그 외에는 BFS를 돌며 BFS가 돌았던 총 횟수가 정답이 된다.

소스 코드 : 

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 68 69 70 71 72 73 74 75 76

#include <iostream> #include <cstdio> #include <queue> #include <algorithm>   using namespace std;   typedef pair<int, int> pii;   char map[30][30]; bool visit[30][30];   int n, cnt; int house[1000];   int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,-1,0,1 };     void bfs(int y, int x) {     queue<pii> q;       if (visit[y][x] || map[y][x] == '0')         return;       cnt++;       q.push(pii(y, x));       while (!q.empty())     {         int hy = q.front().first;         int hx = q.front().second;           q.pop();           if (visit[hy][hx])             continue;           house[cnt - 1]++;         visit[hy][hx] = true;           for (int i = 0; i < 4; i++)         {             int ny = hy + dy[i];             int nx = hx + dx[i];               if ((0 <= ny && ny < n) && (0 <= nx && nx < n && map[ny][nx] == '1'))                 q.push({ ny,nx });         }     } } int main() {     scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%s", map[i]);       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             bfs(i, j);       printf("%d\n", cnt);       sort(house, house + cnt);       for (int i = 0; i < cnt; i++)         printf("%d\n", house[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus