C++)
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#define MAX_NUM 26
using namespace std;
string arr[MAX_NUM];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
vector<int> v;
queue<pair<int,int>> q;
int visited[MAX_NUM][MAX_NUM] = { false };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == '1' && !visited[i][j]) {
visited[i][j] = true;
q.push({ i,j });
int cnt = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
cnt += 1;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (arr[nx][ny] == '1' && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({ nx,ny });
}
}
}
v.push_back(cnt);
}
}
}
sort(v.begin(), v.end());
cout << v.size() << "\n";
for (auto ele : v)
cout << ele << "\n";
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()
n = int(read().rstrip())
arr = []
visited = [[False] * n for _ in range(n)]
for _ in range(n):
arr.append(read().rstrip())
ans = []
for i in range(n):
for j in range(n):
if arr[i][j] == '1' and not visited[i][j]:
visited[i][j] = True
q.append((i,j))
cnt = 0
while q:
x, y = q.popleft()
cnt += 1
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if arr[nx][ny] == '1' and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx,ny))
ans.append(cnt)
ans.sort()
print(len(ans))
for ele in ans:
print(ele)'백준 2 > 그래프' 카테고리의 다른 글
| [백준 11403] 경로 찾기 (0) | 2020.12.08 |
|---|---|
| [백준 2178] 미로 탐색 (C++/Python) (0) | 2020.12.08 |
| [백준 7569] 토마토 (C++/Python) (0) | 2020.12.08 |
| [백준 7576] 토마토 (C++/Python) (0) | 2020.12.08 |
| [백준 10451] 순열 사이클 (0) | 2020.12.08 |