[프로그래머스] 카카오 프렌즈 컬러링북

https://programmers.co.kr/learn/courses/30/lessons/1829#

코딩테스트 연습 - 카카오프렌즈 컬러링북

---

 

-풀이-

주어진 picture 배열을 탐색하며, 0이 아닌수를 만났을때, 해당 지점이 탐색이 완료된 지점이 아닐때( visited[i][j]==false 일때) 해당 지점을 기준으로, bfs를 실행하며, 그 지점과 같은 숫자일때만 탐색을 한다. 이때 탐색하는 동시에 개수를 카운팅 해주며 return을 해주어 답을 갱신해준다. 간단한 bfs문제이다.

 

-시간복잡도-

2차원 배열을 모두 한번씩만 탐색하므로, O(NM) 이 된다.

 

-코드-

#include <vector>
#include<queue>
using namespace std;

bool isIn(int m,int n,int i,int j){
    return 0<=i&&i<m&&0<=j&&j<n;
}

int bfs(vector<vector<int>>& picture,bool visited[][101],int m,int n,int i,int j){
    int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int now=picture[i][j];
    int cnt=0;
    queue<pair<int,int>> q;
    q.push({i,j});
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        cnt++;
        for(int d=0;d<4;d++){
            int nx=x+mv[d][0];
            int ny=y+mv[d][1];
            
            if(isIn(m,n,nx,ny)&&picture[nx][ny]==now&&!visited[nx][ny]){
                visited[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
    return cnt;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    bool visited[101][101]={0};
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(picture[i][j]!=0&&!visited[i][j]){
                visited[i][j]=true;
                max_size_of_one_area=max(max_size_of_one_area,bfs(picture,visited,m,n,i,j));
                number_of_area++;
            }
        }
    }
    
    
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}