https://www.acmicpc.net/problem/1926
아이디어:
1. 문제의 핵심은 BFS를 시작하는 지점을 큐에 넣어주는 것
이중 for문으로 board[i][j] == 1 && vis[i][j] == 0 을 검사해서 큐 push(), vis[i][j] 체크, tmp_area++, num++
2. BFS 과정은 동일하고 큐에서 pop() ~ 인접 지역 큐에 push() 하는 과정에서 tmp_area++
3. 한 그림이 끝났을 때 area = max(area, tmp_area) 로 최대 넓이 계산
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int board[501][501];
int vis[501][501];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int num = 0, area = 0, tmp_area = 0;
queue<pair<int, int>> Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 1 && vis[i][j] == 0) {
vis[i][j] = 1;
Q.push({ i, j });
tmp_area++;
num++;
}
while (!Q.empty()) {
pair<int, int> cur = Q.front();
Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
tmp_area++;
Q.push({ nx, ny });
}
}
area = max(area, tmp_area);
tmp_area = 0;
}
}
cout << num << "\n" << area;
return 0;
}
'algorithm' 카테고리의 다른 글
백준 7576번 토마토 (0) | 2025.04.06 |
---|---|
백준 2178번 미로 탐색 (0) | 2025.04.05 |
넓이우선탐색 BFS (0) | 2025.04.05 |
백준 3986번 좋은 단어 (0) | 2025.04.03 |
백준 4949번 균형잡힌 세상 (0) | 2025.04.03 |