[알고리즘/C++] 프로그래머스 - 카카오프렌즈 컬러링 북 (BFS)

✏️ 해결 방법
굉장히 예전부터 다양한 방법으로 해결해보려고 노력했던 문제인데 이왕 BFS 문제를 푼 김에 초기화하고 같은 방식으로 해결해봤다.
테스트케이스는 통과하는데 제출하면 계속 틀려서 직접 테스트케이스를 만들어서 넣어보다가

이 케이스에서 로직이 틀렸다는 것을 알게 됐다.
map을 사용해서 색상별로 영역의 크기를 저장하고 있었는데 상하좌우로 같은 색상이 연결되어 있어야 한다는 조건을 빼먹었다..

 picture[next.first][next.second] != picture[i][j]

결국 map을 지우고 int형 변수만 사용해서 해결했다.
코드 재활용하다 기본적인걸 놓쳐버렸다.. 😫

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture)
{
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    int area = 0;

    vector<pair<int, int>> dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

    vector<vector<bool>> visit(picture.size(), vector<bool>(picture[0].size(), false));

    for (int i = 0; i < picture.size(); ++i)
    {
        for (int j = 0; j < picture[0].size(); ++j)
        {
            if (picture[i][j] != 0 && visit[i][j] == false)
            {
                visit[i][j] = true;
                area = 1;

                queue<pair<int, int>> waiting;
                waiting.push({i, j});

                while (waiting.empty() == false)
                {
                    pair<int, int> curr = waiting.front();
                    waiting.pop();

                    for (int d = 0; d < dir.size(); ++d)
                    {
                        pair<int, int> next = {curr.first + dir[d].first, curr.second + dir[d].second};

                        if (next.first < 0 || next.first >= picture.size() || next.second < 0 || next.second >= picture[0].size())
                            continue;

                        if (picture[next.first][next.second] == 0 || picture[next.first][next.second] != picture[i][j] || visit[next.first][next.second] == true)
                            continue;

                        waiting.push({next.first, next.second});
                        visit[next.first][next.second] = true;
                        area++;
                    }
                }
            }
            
            if (area > 0) number_of_area++;
            max_size_of_one_area = max(max_size_of_one_area, area);

            area = 0;
        }
    }

    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

✏️ 다른 방법
마찬가지로 DFS로도 해결해봐야겠다.