[BFS]백준 1926번 그림

백준 1926번

그림

BFS로 푸는 문제인데, 생각을 조금 잘못했더니 시간 초과가 걸렸다.

처음에는 그림의 모든 정보를 저장하는게 아니라, 그려진 위치만 따로 저장해 사용하면 훨씬 효율이 높을 거라고 생각했는데 결국 최악의 경우에는 그림 전체가 꽉 차있기 때문에 시간 초과에 걸릴 수 밖에 없었다.

따라서 처음부터 500 * 500 사이즈의 배열을 만들고 전체 그림을 입력받아 기준이 되는 좌표의 상 하 좌 우 만 보게 하였다.

기본적으로, 그림 전체를 순회하면서

만약 { 그림이 그려져있고 아직 방문된 적이 없다면 } 해당 좌표는 기준점이 된다.

기준점을 queue에 넣고, 해당 기준점의 상 하 좌 우 를 살펴 {그림이 그려져있고 아직 방문된 적이 없다면} queue에 추가한다. queue에 추가한 뒤에는 queue가 빌 때까지 queue의 front를 기준점으로 삼아 상 하 좌 우를 탐색한다. 이 때 큐에 추가되는 횟수가 해당 기준점으로부터 만들어진 그림의 넓이가 된다.

queue가 비었다면 해당 기준점으로부터는 더 이상 연결된 그림을 찾을 수 없다는 뜻이기 때문에 다른 기준점을 찾기 위해 그림 전체를 마저 순회한다. 이 때 그룹의 개수를 count 한다.

처음 벡터를 이용해 시간초과가 난 코드

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int height, width; cin >> height >> width;
    vector<pair<int,int> > pictures(250001);
    int v_count = 0;
      for(int i=0; i < height; i++){
        for(int j=0;j<width;j++){
            int temp; cin >> temp;
            if(temp==1){
               // pictures.push_back(make_pair(i,j));
                pictures[v_count]=make_pair(i,j);
                v_count++;
            }
        }
    }
    vector<bool> groupped(v_count,false);
    int count =0;
    int maxArea = -1;
    for(int i=0;i<v_count;i++){
        if(!groupped[i]){
        queue<pair<int, int> > q;
        q.push(pictures[i]);
        groupped[i]=true;
       // cout << "leader is " << pictures[i].first << " " << pictures[i].second << endl;
        int area = 1;
        while(!q.empty()){
            pair<int, int> tmp = q.front();
            q.pop();
            for(int j=0;j<v_count;j++){
                if(!groupped[j]){
                    int gap_x = abs(tmp.first - pictures[j].first);
                    int gap_y = abs(tmp.second - pictures[j].second);
                    if((gap_x==1 && gap_y==0)||(gap_x==0&&gap_y==1)){
                        q.push(pictures[j]);
                     //   cout << pictures[j].first << " " << pictures[j].second << endl;
                        groupped[j]=true;
                        area++;
                    }
                }
            }
        }
        count ++;
        if(maxArea <= area) maxArea=area;
       // cout << "group is " << count << " and area is " << area << endl;
        }
    }
    if(count==0) maxArea=0;
    cout << count << endl << maxArea << endl;
    
}

배열을 이용한 코드

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int height, width; cin >> height >> width;
   // int picture[501][501]={-1};
    int picture[501][501]={-1};
    int visited[501][501]= {0};
      for(int i=0; i < height; i++){
        for(int j=0;j<width;j++){
            cin >> picture[i][j];
        }
    }
    //input finished
    int maxArea=0;
    int count=0;
    for(int i=0;i<height;i++){
        for(int j=0;j<width;j++){
            if(picture[i][j]==1 && visited[i][j]==0){
                queue<pair<int,int> > q;
                q.push(make_pair(i,j));
                visited[i][j]=1;
                int area = 1;
                count ++;
                while(!q.empty()){
                    pair<int,int> tmp = q.front();
                    q.pop();
                    if(picture[tmp.first+1][tmp.second]==1&&visited[tmp.first+1][tmp.second]==0){
                        q.push(make_pair(tmp.first+1,tmp.second));
                        visited[tmp.first+1][tmp.second]=1;
                        area++;
                    }
                     if(picture[tmp.first][tmp.second+1]==1&&visited[tmp.first][tmp.second+1]==0){
                        q.push(make_pair(tmp.first,tmp.second+1));
                        visited[tmp.first][tmp.second+1]=1;
                        area++;
                    }
                     if(tmp.first-1>=0&&picture[tmp.first-1][tmp.second]==1&&visited[tmp.first-1][tmp.second]==0){
                        q.push(make_pair(tmp.first-1,tmp.second));
                        visited[tmp.first-1][tmp.second]=1;
                        area++;
                    }
                     if(tmp.second-1>=0&&picture[tmp.first][tmp.second-1]==1&&visited[tmp.first][tmp.second-1]==0){
                        q.push(make_pair(tmp.first,tmp.second-1));
                        visited[tmp.first][tmp.second-1]=1;
                        area++;
                    }
                }
                if(maxArea<=area){
                    maxArea=area;
                }
            }
        }
    }
    cout << count << endl << maxArea << endl;
}