백준 1926 그림

문제링크 : https://www.acmicpc.net/problem/1926

아이디어

• BFS 사용해서 연결된 노드 구하기(Flood Fill)
  • 전체 노드 순회하면서 체크 안되어있는 노드 발견할경우 BFS 수행
    • 이떄마다 전체 그림 카운트 수 증가
    • 그리고 그림 가장 넓은값 구하기
      

시간복잡도 계산

• BFS : O(V+E)
  • V : 모든 노드수 : O(NM)
  • E : 노드에서 간선수 4방향 : O(4NM)
  • N과 M 최대값이라고 가정시
  • 총합 : O(5N^2)
    • O(5*N^2) = 5 * 25e4 : 125e4 = 1.25e6

자료구조

• 그림 개수 cnt : 최대 N^2 = 25e4 : INT 가능
• 그림 최대 크기 maxv : 최대 N^2 = 25e4 : INT 가능
• BFS에서 사용하는 큐 queue<pair<int, int>>

코드(C++)

#include <iostream>
#include <queue>
 
using namespace std;
 
int map[510][510];
bool chk[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int N,M;
 
int bfs(int y, int x) {
    int cnt=0; // 그림 크기
    
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    chk[y][x] =1;
    
    while(!q.empty()) {
        auto eq = q.front(); q.pop();
        int ey = eq.first;
        int ex = eq.second;
        cnt++; // 그림 크기 증가
        
        for(int k=0; k<4; k++) {
            int ny = ey + dy[k];
            int nx = ex + dx[k];
            if(ny>=0 && ny < N && nx>=0 && nx < M) {
                if(map[ny][nx] == 1 && chk[ny][nx] == 0) {
                    chk[ny][nx] = 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
    
    return cnt;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&chk[0][0], &chk[509][510], 0);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    int cnt=0;
    int maxv= 0;
    
    // 체크되어있지 않은 경우 bfs 수행
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(map[j][i] == 1 && chk[j][i] == false) {
                maxv = max(maxv, bfs(j,i));
                cnt++;
            }
        }
    }
    
    cout << cnt << '\n';
    cout << maxv << '\n';
    
    
    return 0;
}
 

문제유형

• BFS - Flood Fill
  • 이어져있는 노드를 연결하는 문제
  • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

• https://www.acmicpc.net/problem/1926
• https://www.acmicpc.net/problem/2638