[C++]카카오프렌즈 컬러링북(프로그래머스 2레벨)

 

 
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int bfs(vector<int> loc, queue<vector<int>>* que, vector<vector<bool>>& boolvec, vector<vector<int>>& picture)
{
    int size = 0;
    int x = loc[0];
    int y = loc[1];
    boolvec[x][y] = true;
    que->push(loc);
    int number = picture[x][y];
 
    while (!que->empty())
    {
    	// 양옆위아래 다 확인
        if (x + 1 < picture.size())
            if (number == picture[x + 1][y] && !boolvec[x + 1][y])
            {
                boolvec[x + 1][y] = true;
                que->push({ x + 1,y });
            }
 
        if (y + 1 < picture[0].size())
            if (number == picture[x][y + 1] && !boolvec[x][y + 1])
            {
                boolvec[x][y + 1] = true;
                que->push({ x,y + 1 });
            }
 
        if (x > 0)
            if (number == picture[x - 1][y] && !boolvec[x - 1][y])
            {
                boolvec[x - 1][y] = true;
                que->push({ x - 1,y });
            }
 
        if (y > 0)
            if (number == picture[x][y - 1] && !boolvec[x][y - 1])
            {
                boolvec[x][y - 1] = true;
                que->push({ x,y - 1 });
            }
 
        que->pop();
 
        if (!que->empty())
        {
            vector<int> xy = que->front();
            x = xy[0];
            y = xy[1];
        }
 
        ++size;
    }
 
    return size;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture)
{
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    queue<vector<int>> que = {};
    vector<vector<bool>> boolvec = {};
    vector<int> number = {};
    vector<vector<int>> location = {};
    vector<int> bfsresult = {};
    vector<int> result = {};
    bool zero = false;
 
    boolvec.resize(m);
 
    for (int i = 0; i < m; ++i)
    {
        boolvec[i].resize(n);
 
        for (int j = 0; j < n; ++j)
        {
            boolvec[i][j] = false;
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (picture[i][j] && !boolvec[i][j])
                bfsresult.push_back(bfs({ i,j }, &que, boolvec, picture));
        }
    }
 
    result.push_back(bfsresult.size());
 
    result.push_back(*max_element(bfsresult.begin(), bfsresult.end()));
 
    return result;
}

너무 오랜만에 본 탐색... 처음에 어떻게 해야 하나... 엄청 고민했다 진짜로...

하기 전에 BSF 탐색, DSF 탐색, 스택, 큐 좀 제대로 보고 하는 것을 추천한다.

 

BSF탐색 - 너비 우선 탐색(Breadth-First Search)

근처에 있는 모든 경로를 하나씩 찾아서 검사한다. (넓게 탐색)

이 탐색을 사용할 때는 큐를 이용해서 탐색한다.

여기서 큐는 선입선출 들어간 것이 먼저 나오는 구조이다.

BSF탐색은 처음에 탐색을 시작할 때 모든 경로를 큐에 넣어놓고 첫 경로를 지우고 그다음 경로로 가 그 경로의 모든 경로를 넣어놓고 하기 때문에 특정 조건의 최단 경로 알고리즘을 계산할 때도 사용

 

DSF탐색 - 깊이 우선 탐색(Depth-First Search)

한 경로의 끝까지 모두 탐색하고 나서 다음 경로를 탐색한다.

이 탐색을 사용할 때는 스택이나 재귀함수를 이용해서 탐색한다.

여기서 스택은 선입후출 들어간 것이 제일 마지막으로 나오는 구조이다.

DSF탐색은 모든 경로를 탐색할 때 사용하기 때문에 BSF 탐색보다는 느리다.