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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다.

 

문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다.

 

그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.

(다시 탐색을 하지 않도록 표시를 해야한다)

 

연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다.

 

만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다.

 

마지막으로 구한 영역의 수와 최대 영역의 크기를 return하면 된다.

 

 

​

[아이디어 정리]

1. 0이 아닌 부분 즉, 색칠된 영역을 만나면 영역의 수를 1 늘리고 BFS로 영역의 탐색을 시작한다.
2. 이때 영역을 탐색하면서 방문한적이 있는 영역은 방문했다는 표시를 남긴다.
3. 연결된 영역의 크기를 구하고 이 영역의 크기가 가장 큰지 저장된 값과 비교한다.
4. 계산된 값을 return한다.

 

 

Code

 

 

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

int BFS(int y, int x, vector<vector<int>> &picture,int m,int n)
{
    int dy[4]={1,-1,0,0};
    int dx[4]={0,0,1,-1};
    int nowNum=picture[y][x],ny,nx;
    int retAns=1;
    queue<pair<int,int>> q;
    q.push(make_pair(y,x));
    picture[y][x]=0;
    pair<int,int> np;
    while(!q.empty())
    {
        np=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            ny=np.first+dy[i];
            nx=np.second+dx[i];
            if (ny>=0&&ny<m&&nx>=0&&nx<n&&picture[ny][nx]==nowNum)
            {
                picture[ny][nx]=0;
                q.push(make_pair(ny,nx));
                retAns+=1;
            }
        }
    }
    return retAns;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    
    vector<int> answer(2,0);
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n; j++)
        {
            if (picture[i][j]!=0)
            {
                answer[0]+=1;
                answer[1]=max(answer[1],BFS(i,j,picture,m,n));
            }
        }
    }
    return answer;
}

 

---

BFS나 DFS등 탐색을 하는 방법을 구현할 수 있다면 쉽게 풀 수 있는 문제였다

 

프로그래머스