bfs/dfs를 꾸준히 안 풀면 감을 잃을 것 같아서 풀어봤다. 자만하다가 결국 내 힘만으로 풀지 못해서 이전에 다른 bfs문제를 풀었던 방식을 참고했다. ㅜㅜ
그래프의 인접노드를 확인하기 위해서 xs와 xy배열을 만들었다. bfs 내에서 총 4번 반복하며 좌우상하 노드를 탐색하게 된다. bfs의 구성은 간단했는데 main에서 이중반복을 돌리지 않고 bfs(graph[1][1])만 작성해서 계속 헤맸다. 코드 작성하면서도 이런 코드라면 한 단지의 수밖에 알수없고 그마저도 첫 노드의 값이 0이면 아무 동작하지 않을거라고 생각했는데 내 생각이 맞았다. dfs와 개념을 혼동했고 그마저도 제대로 된 코드가 아니었기에 문제에 맞춰진 공부를 했다는 생각이 들었다.
내일은 클러스터 나가서 처음으로 본과정 과제 도전하려고 한다. 풀기 전에 bfs/dfs한문제 풀어야겠다.
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int graph[26][26];
bool visit[26][26];
int n;
int now = 0;
int dong[25 * 25 + 1];
int xs[4] = { 0,0,1,-1 };
int ys[4] = { 1,-1,0,0 };
void bfs(int x, int y)
{
deque<pair<int, int>>q;
q.push_back({ x,y });
visit[x][y] = true;
dong[now]++;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop_front();
for (int i = 0; i < 4; i++)
{
int nx = x + xs[i];
int ny = y + ys[i];
if (nx > 0 && nx <= n && ny > 0 && ny <= n)
{
if (visit[nx][ny] == false && graph[nx][ny] == 1)
{
visit[nx][ny] = true;
dong[now]++;
q.push_back({nx, ny});
}
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++)
{
graph[i][j + 1] = s[j] - '0';
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (visit[i + 1][j + 1] == false && graph[i + 1][j + 1] == 1)
{
now++;
bfs(i + 1, j + 1);
}
}
}
sort(dong + 1, dong + now + 1);
cout << now << '\n';
for (int i = 1; i <= now; i++)
{
cout << dong[i] << '\n';
}
}