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

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/1829

프로그래머스

---

 

 

해결전략

 

너비우선탐색 BFS

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

vector<vector<int>> v, ch;
int NumOfArea = 0;
int MaxOneArea = 0;

void BFS(int y, int x, int m, int n)
{
    queue<pair<int, int>> Q;
    Q.push({ y, x });
    ch[y][x] = 1;

    int cnt = 1;
    while(!Q.empty())
    {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dirY[i];
            int nx = x + dirX[i];

            if (ny < 0 || m <= ny || nx < 0 || n <= nx) continue;
            if (v[ny][nx] != v[y][x]) continue; // 다른영역이면 continue

            if (ch[ny][nx] == 0){
                ch[ny][nx] = ch[y][x] + 1;
                Q.push({ ny, nx });

                cnt++; // 영역 내 개수 카운팅
            }
        }
    }
    
    MaxOneArea = max(MaxOneArea, cnt);
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    ch.resize(m, vector<int>(n));
    v.resize(m, vector<int>(n));
    v = picture;

    for(int y = 0; y < m; y++){
        for (int x = 0; x < n; x++) {
            if (picture[y][x] == 0) continue; // 0인 경우, 색칠하지 않는다.

        	if(ch[y][x] == 0){
                BFS(y, x, m, n);
                NumOfArea++;
            }
        }
    }

    vector<int> answer(2);
    answer[0] = NumOfArea;
    answer[1] = MaxOneArea;

    cout << answer[0] << ", " << answer[1];

    return answer;
}

int main(){
    vector<vector<int>> testcase1 = { {1, 1, 1, 0} ,{1, 2, 2, 0} ,{1, 0, 0, 1},{0, 0, 0, 1},{0, 0, 0, 3},{0, 0, 0, 3} };
    solution(6, 4, testcase1);
}

 

 

---