(프로그래머스 c++ KAKAO)카카오 프렌즈 컬러링북

BFS를 이용하여 문제를 풀었다.

이중 for문을 사용하여 picture 벡터를 순회하였다.

bfs함수를 통해 순회한 위치에는 -1을 넣어 탐색하지 않도록 설정한다.

현재 picture[i][j]가 0이거나 -1이면 무시하도록 하자..!

0, -1이 아니면 영역의 수를 나타내는 number_of_area를 1씩 늘려주고,

현재 picture[i][j] 원소의 개수를 bfs 함수를 통해 세어본다..!

 

bfs(int m, int n, int x, int y, vector<vector<int>>& picture, int target)

-->

m과 n은 그림의 크기,

x와 y는 현재 순회하고 있는 인덱스,

picture는 그림.

 

우선 종료조건을 만들어주자..!

x ,y 가 0보다 작거나 x, y가 각각 m, n과 같거나, target과 pictur[x][y]가 서로 다르면 return을 한다.

1)x, y가 0보다 작은 경우

: 그림의 상하좌우를 검사하여 같은 영역인지 확인해야 한다.

 코드에서 볼 수 있듯이 상, 좌를 검사하려면 x - 1, y - 1을 해줘야 한다.

 하지만 배열의 음수는 없고, 확인할 수 없으므로 return 하도록 해주었다.

 

2)x, y가 각각 m, n과 같은 경우

: 각 행렬의 끝에 다다르면 return 하도록 해주었다.

 

3)target != picture[x][y]

: 상하좌우가 같은 요소인 경우 순회해야 하므로 같지 않으면 return 하도록 하였다.

 

이제 상하좌우를 검사하기 위해 해당 위치에서 상하좌우에 해당하는 영역을 x, y에 넘겨주고

순회하도록 한다.

그리고 마지막에 상하좌우 + 1을 해준 값을 리턴하면

알아서 영역의 최대 크기를 구할 수 있따..!

 

#include <vector>

using namespace std;
int bfs(int m, int n, int x, int y, vector<vector<int>>& picture, int target);

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

int bfs(int m, int n, int x, int y, vector<vector<int>>& picture, int target)
{
    if(x < 0 || y < 0 || x == m || y == n || target != picture[x][y])
        return 0;
    picture[x][y] = -1;
    
    int up = bfs(m, n, x - 1, y, picture, target);
    int down = bfs(m, n, x + 1, y, picture, target);
    int left = bfs(m, n, x, y - 1, picture, target);
    int right = bfs(m, n, x, y + 1, picture, target);
    
    return up + down + left + right + 1;
}