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

문제 링크

카카오프렌즈 컬러링북

풀이

DFS, BFS로 푸는 문제

1. 방문하지 않았고, picture[i][j]가 0이 아니라면 number_of_area++를 해주고, max_size_of_one_area를 최댓값으로 갱신한다.
2. BFS 함수는 dx와 dy를 통해 상하좌우를 비교하여 picture[y][x] 값과 picture[ny][nx] 값이 같다면 ans++를 해주고 return해준다.

⚠ 주의

전역변수로 쓰니까 틀렸다고 나와서 함수 안에 넣어주니 통과했다.

코드

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int BFS(vector<vector<int>> picture,vector<vector<int>> &visit, int y, int x)
{
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    
    int ans=1;
    queue<pair<int,int>> q;
    q.push({y,x});
    visit[y][x]=1;
    while(!q.empty())
    {
        int ty=q.front().first;
        int tx=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ny=ty+dy[i];
            int nx=tx+dx[i];
            if(ny<0||ny>=picture.size()||nx<0||nx>=picture[0].size()) continue;
            if(visit[ny][nx]==1) continue;
            if(picture[ny][nx]==picture[y][x]) {
                ans++;
                visit[ny][nx]=1;
                q.push({ny,nx});
            }
        }
    }
    cout<<y<<" "<<x<<" "<<ans<<endl;
    return ans;
}

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