[C++] 프로그래머스 카카오프렌즈 컬러링북 풀이 (BFS)

주어진 그림이 몇 개의 영역으로 나눠져 있으며 제일 넓은 부분은 어디인지 구하는 문제

 

---

문제의 조건

 

1. 그림의 세로 m, 가로 n, m x n 2차원 배열 picture가 주어짐

 

2. 주어진 그림에서 상하좌우 방향으로 연속한 숫자들만 같은 영역으로 침

-> BFS로 연속한 같은 숫자끼리의 넓이를 구하자 

 

3. 영역이 몇 개인지, 그 중 가장 넓은 영역 크기는 몇인지 구하기 

 

4. 전역변수는 solution 함수 안에서 초기화 해 주어야 함 

 

---

#include <vector>
#include <memory.h>
#include <queue>

using namespace std;

int dir[4][2];

vector<pair<int, int>> Pixels(pair<int, int> curPos, int m, int n)
{
    vector<pair<int, int>> pixels;
    for (int i = 0; 4 > i; i++)
    {
        pair<int, int> pos;
        pos = make_pair(curPos.first + dir[i][1], curPos.second + dir[i][0]);
        //위치 범위 설정 
        if (0 <= pos.first && 0 <= pos.second && n > pos.first && m > pos.second)
            pixels.push_back(pos);
    }
    
    return pixels;
}

vector<vector<bool>> visited;
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    dir[0][0] = -1;
    dir[0][1] = 0;
    dir[1][0] = 1;
    dir[1][1] = 0;
    dir[2][0] = 0;
    dir[2][1] = -1;
    dir[3][0] = 0;
    dir[3][1] = 1;
    visited.assign(100, vector<bool>(100, false));
    
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    for (int y = 0; picture.size() > y; y++)
    {
        for (int x = 0; picture[y].size() > x; x++)
        {
            if (!visited[y][x] && 0 < picture[y][x])
            {
                queue<pair<int, int>> nonVisited;
                int range = 0;
                int curNum = picture[y][x];
                
                nonVisited.push(make_pair(x, y));
                
                while (!nonVisited.empty())
                {
                    pair<int, int> curPixel = nonVisited.front();
                    nonVisited.pop();
                    
                    //현재 픽셀을 방문하지 않았으면 방문 표시
                    if (!visited[curPixel.second][curPixel.first] && curNum == picture[curPixel.second][curPixel.first])
                    {
                        range++;
                        visited[curPixel.second][curPixel.first] = true;
                        
                        //인접한 픽셀 중에서 방문하지 않은 픽셀이 있으면 큐에 추가
                        vector<pair<int, int>> nearby = Pixels(curPixel, m, n);
                        for (auto& p: nearby)
                        {
                            if (!visited[p.second][p.first])
                                nonVisited.push(p);
                        }
                    }
                }
                
                max_size_of_one_area = max(max_size_of_one_area, range);
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

휴... Pixels 함수에서 picture 인덱스 범위보다 커질 때 범위 설정을 제대로 안 해줘서 계속 out of index 에러가 나서 몇 시간 날린 문제 ㅠ.ㅠ

첨엔 저거 생각도 못 하고 왜 안되지 하다가 하나하나 디버깅 하면서 깨달았습니다...

정말 ㅈ같은 문제였어 

 

그리고 전역변수는 꼭 함수 안에서 초기화를 해 주어야 통과됩니다.