백준 1926 그림문제
#include <bits/stdc++.h>
using namespace std;
# define X first
# define Y second
int row;
int col;
//지도
int board[502][502];
//방문했는지 확인할 지도.
bool vis[502][502];
//dx, dy는 상하좌우를 확인할 때 쓰임
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//biggest = 가장 큰 그림, count = 그림의 개수
int biggest = 0;
int count = 0;
cin >> row >> col;
//지도를 배열에 채워넣음
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
cin >> board[i][j];
}
}
queue<pair<int, int>> Q;
for (int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
//i, j번째가 비어 있거나 방문한 곳이라면 continue;
if (board[i][j] == 0 || vis[i][j])
continue;
count++; //BFS가 시작될 때마다 count += 1;
vis[i][j] = 1; //방문했다는 표시
Q.push({i, j}); //큐에 좌표를 담음.
int area = 0;
while (!Q.empty()) { //좌표를 기준으로 상하좌우 확인.
area++; //일단 지금 있는 칸을 count.
pair<int, int> cur = Q.front(); //현재 위치 저장.
Q.pop();
for (int dir = 0; dir < 4; dir++) {
//46 ~ 51 번째 줄은 상하좌우를 확인하는 코드.
//nx, ny가 범위를 벗어나는 경우도 고려.
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= row || ny >= col)
continue;
if (vis[nx][ny] || board[nx][ny] != 1)
continue;
vis[nx][ny] = 1; //visit했다는 표시.
Q.push({nx, ny});
}
}
biggest = max(biggest, area);
}
}
cout << count << '\n' << biggest;
return 0;
}
'Algorithm' 카테고리의 다른 글
BOJ 7576 토마토 c++ (0) | 2020.07.10 |
---|---|
BOJ 2178 미로 탐색 c++ (0) | 2020.07.10 |
BOJ 10866 덱 (C++) (0) | 2020.07.06 |
BOJ 10845 큐 C++ (0) | 2020.07.06 |
BOJ 4949 균형잡힌세상(C++) (0) | 2020.07.05 |
최근댓글