백준 2667 단지번호붙히기

문제 링크 : https://www.acmicpc.net/problem/2667

※선행해야 할 알고리즘 : BFS/DFS

Algorithm : BFS/DFS 를 활용하여 군집을 찾아 군집의 개수와 군집의 원소 개수를 오름차순으로 출력해라

1. 지도를 입력 후, 지도에서 1이 입력된 인덱스를 찾아 반환한다.

2. 반환된 인덱스를 기준으로 아래, 왼쪽, 오른쪽을 BFS하며 count 한다. 이 때, 1을 찾아 방문을 했기에 count의 초기값은 1이다. 또한 방문한 곳들은 지도를 0으로 설정하여 다시 들리지 못하게 한다.

3. 해당 count를 vector에 삽입하고, 1~3을 지도에 1이 더 이상 없을 때까지 반복한다.

예를 들어, 입력 예제 본다면

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000

에서 1~2를 진행하였을 땐 아래와 같이 될 것이다.

0000100

0000101

0000101

0000111

0100000

0111110

0111000

그 후, 1~2를 다시 반복할 땐 파란색 1 을 발견하여 해당 군집의 count를 벡터에 삽입한다.

4. 마지막으로 vector를 오름차순으로 정렬해 준 후, vector.size()를 삽입하여 출력한다.

5. 1~4를 queue를 활용하여 BFS를 진행하면 다음과 같다.

#include<iostream> #include<vector> #include<queue> #include<algorithm> #include<cstdio> using namespace std; vector<vector<int>> G; vector<vector<bool>> check; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; pair<int, int> search(vector<vector<int>>G) { for (int i = 0; i < G.size(); i++) for (int j = 0; j < G[i].size();j++) if (G[i][j] == 1) return { i,j }; return { -1,-1 }; } vector<int> sol(vector<vector<int>> G, vector<vector<bool>> check) { vector<int>sol; queue<pair<int, int>> q; while (1) { auto where_1 = search(G); if (where_1.first == -1 && where_1.second == -1) break; q.push({ where_1.first,where_1.second}); int count = 1; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); check[x][y] = true; G[x][y] = 0; for (int i = 0; i < 4; i++) { int now_x = x + dx[i]; int now_y = y + dy[i]; if (now_x >= 0 && now_y >= 0 && now_x < G.size() && now_y < G.size() && !check[now_x][now_y] && G[now_x][now_y] == 1) { G[now_x][now_y] = 0; check[now_x][now_y] = true; q.push({ now_x, now_y }); count++; } } } sol.push_back(count); count = 0; } sort(sol.begin(), sol.end()); sol.push_back(sol.size()); return sol; } int main() { int N; cin >> N; G.resize(N); check.resize(N); for (int i = 0; i < N; i++) { check[i].resize(N, true); G[i].resize(N); for (int j = 0; j < N; j++) { scanf("%1d", &G[i][j]); if (G[i][j]) check[i][j] = false; } } auto s = sol(G, check); if (s.size() == 0) cout << 0 << endl; else { cout << s[s.size() - 1] << endl; for (int i = 0; i < s.size() - 1; i++) cout << s[i] << endl; } return 0; }