[ 백준 1926 ] 그림 (C++)

[문제보기]

 

[해결과정]

 

 1. input

   -> n, m (세로, 가로) 변수, arr (map 2차원 배열)

 

 2. arr 맵을 돌며, arr[i][j]==1 이고, check[i][j]==0 (방문하지않음) 이라면, 진입

   -> group(집합 갯수)를 +1 시키고, cnt(원소 갯수)를 1로 초기화한다.

     -> ★★★그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt;

   -> check[i][j]==1로 방문체크를 한다.

   -> queue에 i,j좌표를 삽입하고, BFS()로 진입한다.

 

 3. BFS

   -> 주변 4방향을 탐색하며, arr[i][j]==1이고, check[i][j]==0 인 곳 진입

   -> cnt(원소 갯수)++;

     -> 그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt;

   -> queue에 i,j좌표를 삽입한다.

 

  4. ouput

   -> group(집합 갯수) == 0 이면 cnt 또한 0...

   -> 위와 같은 경우가 아니라면, group과 cnt 출력.

 

[소스코드]

/*
    BOJ 1926 - 그림
    Created by haejun on 2020/02/24
*/
#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX = 502;
 
int arr[MAX][MAX];
int check[MAX][MAX];
int n, m;
 
struct coor {
    int y;
    int x;
};
int group;
int cnt;
int maxCnt;
 
queue <coor> q;
 
//inside check, dir
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = {-1,1,0,0};
int dx[4] = { 0,0,-1,1 };
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && arr[ny][nx] == 1 && check[ny][nx] == 0) {
                check[ny][nx] = 1;
                cnt++;
                if (cnt > maxCnt) maxCnt = cnt;
                q.push({ ny,nx });
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1 && check[i][j]==0) {
                check[i][j] = 1;
                group++;
                cnt = 0;
                cnt++;
                if (cnt > maxCnt) maxCnt = cnt;
                q.push({ i,j });
                bfs();
            }
        }
    }
 
    if (group == 0) {
        cout << "0\n0";
    }
    else {
        cout << group << "\n";
        cout << maxCnt << "\n";
    }
 
 
 
    return 0;
}

[해결 과정 중 실수한 부분]

 전형적인 BFS() 문제이다. 기본적인 BFS문제이지만, 2번만에 맞췄다.... 사유는 위에 별표 친 곳! 그 부분을 빠뜨려서, 한 번 틀렸다... 기초적이고 기본적인 문제라고 해서 한 번에 다 맞추는 것은 쉬운 일이 아니다...

 

[관련 문제 혹은 비슷한 문제]

 BFS