그림_백준1926_BFS

-문제-

 

-문제 접근-

 

이 문제는 2차원 보드에서 1로 표시된 영역을 찾고, 이들로 이루어진 연결된 영역의 개수와 그 중에서 가장 큰 영역의

크기를 구하는 문제 입니다.

 

 

• 입력:
  • n x m 크기의 격자가 주어지며, 각 칸은 0 또는 1의 값을 가집니다.
• 문제 접근:
  • 탐색 과정에서 같은 칸을 여러 번 방문하지 않도록 하기 위해 방문 여부를 체크할 방문 배열 필요
  • 순회
    • 격자의 각 칸을 순회하면서, 만약 해당 칸이 1이고 아직 방문하지 않았다면, 새로운 영역의 시작점으로 간주
    • 새로운 영역이 발견될 때마다 영역의 개수(num)를 증가
  • 영역 탐색 (BFS):
    • BFS(너비 우선 탐색)를 이용하여 해당 영역의 연결된 모든 1들을 방문
      • 시작점을 큐에 넣고, 큐가 빌 때까지 반복하며 4방향(상, 하, 좌, 우)으로 인접한 칸들을 검사
      • 범위 검사를 통해 격자를 벗어나지 않도록 하고, 이미 방문했거나 1이 아닌 경우는 스킵
    • 탐색하는 동안 각 영역에 속한 칸의 수를 area 변수에 누적
    • 각 영역의 탐색이 마칠 때 마다 최대 면적(mx)을 갱신
• 출력:
  • 영역의 총 개수와 최대 면적을 출력

 

-전체 코드-

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int board[502][502];
bool vis[502] [502];

int n, m;
int dx[4] = {1, 0, -1, 0}; 
int dy[4] ={0, 1, 0, -1};

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            cin >> board[i][j];
    }
    
    int mx = 0;
    int num = 0;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j] == 0 || vis[i][j]) continue;
        num++;
        queue<pair<int,int>> Q;
        vis[i][j] = 1;
        Q.push({i,j});
        
        int area = 0;
        while(!Q.empty()){
            area++;
            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});
            }
        }
        mx = max(mx, area);
    }
    }
    cout << num << "\n" << mx;
}

 

 

 

-코드 설명-

 

dx와 dy 배열: 상하좌우 4방향으로의 이동을 위해 정의된 배열

 

중첩 for문: 각 칸을 순회하면서 칸의 값이 0이거나 이미 방문한 경우 건너뛰고 새로운 영역의 시작점을 1 증가

 

BFS: 큐가 빌 때까지 front를 꺼내 현재 위치로 설정하고 칸의 개수(area)를 1 증가 후 4방향(상, 하, 좌, 우) 탐색

방문한 칸이거나 값이 1이 아니면 건너 뛰고 조건 만족 시 해당 칸을 방문 처리하고 큐에 추가

 

max(mx, area): 한 영역의 탐색이 끝나면 현재 영역의 면적(area)와 기존 최대 면적(mx)를 비교하여 큰 값으로 갱신