BOJ : 1926 그림 (C++)

김정욱·2020년 10월 27일
0

Algorithm - 문제

목록 보기
23/249

문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
#define X first
#define Y second
int board[502][502];
bool vis[502][502];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N,M;
    int max_width=0, cur_width=0, tot_cnt=0;

    // 그림 입력
    cin >> N >> M;
    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(vis[i][j] || board[i][j] != 1) continue;
            tot_cnt++;
            queue<pair<int,int>> Q;
            Q.push({i,j});
            vis[i][j] = 1;
            cur_width++;
            while(!Q.empty())
            {
                pair<int,int> cur = Q.front(); Q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int nx=cur.X + dx[dir];
                    int ny=cur.Y + dy[dir];
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if(vis[nx][ny] || board[nx][ny] != 1) continue;
                    vis[nx][ny] = 1;
                    Q.push({nx,ny});
                    cur_width++;
                }
            }
            if(cur_width > max_width) max_width = cur_width;
            cur_width=0;
        }
    }
    cout << tot_cnt << '\n' << max_width;
}
  • BFS 대표문제
profile
Developer & PhotoGrapher

0개의 댓글