풀이 방법
bfs 문제로 맵 전체를 for 문을 돌며 board[y][x] 가 1이고 visited[y][x]가 -1 인 점을 bfs(y, x)를 호출하여
그 점과 연결된 점들을 방문하여 넓이를 구하고 가장 큰 곳이면 답을 변수 ans에 저장한다.
그리고 bfs가 호출 될 때마다 그림의 개수 카운터를 증가시킨 후 출력한다.
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0, cnt = 0;
int board[501][501];
int visited[501][501];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void bfs(int y,int x) {
int wd = 1;
queue<pair<int, int>> q;
visited[y][x] = 1;
q.push(make_pair(y, x));
while(!q.empty()) {
int yy = q.front().first;
int xx = q.front().second;
q.pop();
for (int i = 0;i < 4;i++) {
int ny = yy + dy[i];
int nx = xx + dx[i];
if (ny >= 0 && ny < n && nx >= 0 && nx < m && board[ny][nx] == 1) {
if (visited[ny][nx] == -1) {
visited[ny][nx] = 1;
q.push(make_pair(ny, nx));
wd++;
}
}
}
}
ans = max(ans, wd);
}
int main() {
cin >> n >> m;
memset(visited, -1 ,sizeof(visited));
for (int i = 0;i < n;i++) {
for (int k = 0;k < m;k++) {
cin >> board[i][k];
}
}
for (int i = 0;i < n;i++) {
for (int k = 0;k < m;k++) {
if (board[i][k] == 1) {
if (visited[i][k] == -1) {
cnt++;
bfs(i, k);
}
}
}
}
cout << cnt << endl << ans;
}
'Algorithm' 카테고리의 다른 글
[백준] 양 3184번 (c++) (0) | 2022.11.02 |
---|---|
[백준] 이동하기 11048번 (c++) (0) | 2022.10.06 |
[백준] 동전1 2293번 (c++) (0) | 2022.08.02 |
[백준] 계단오르기 2579번 (c++) (0) | 2022.07.21 |
[백준] N-Queen 9663번 (c++) (0) | 2022.07.15 |