BOJ 1926 그림 c++

Algorithm / / 2020. 7. 10. 02:10

백준 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
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
// custom