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

(주)그렙

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

(C++)

(글쓴날 : 2020.06.07)

 

---

* programmers, 프로그래머스 문제 C++ 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 카카오프렌즈 컬러링북

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

2차원 형태의 컬러링 북이 주어질 때, 색깔별로 다른 구간의 수와, 가장 넓은 범위의 크기를 구하는 문제입니다.

 

저의 경우, BFS를 적용하였으며, C++을 사용했습니다.

방문 기록을 체크할 컬러링 북과 동일한 크기의 2차원 vector를 만든 뒤 큐를 이용한 BFS를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <vector>
#include <iostream>
#include <queue>
#include <utility>
 
using namespace std;
 
int max_size_of_one_area;
vector<vector<bool>> visit;
 
void BFS(int color, int dx[], int dy[], vector<vector<int>> &picture, int m, int n, int x, int y)
{
    queue<pair<int, int>> q;
 
    q.push({x, y});
 
    int i = 0, j = 0;
    int ii = 0, jj = 0;
    int count = 0;
 
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
 
        q.pop();
 
        if (visit[i][j])
            continue;
 
        visit[i][j] = true;
        count++;
 
        for (int way = 0; way < 4; way++)
        {
            ii = i + dx[way];
            jj = j + dy[way];
 
            if (ii < 0 || ii > m - 1 || jj < 0 || jj > n - 1)
                continue;
 
            if (picture[ii][jj] != color)
                continue;
 
            q.push({ii, jj});
        }
    }
 
    if (max_size_of_one_area < count)
        max_size_of_one_area = count;
}
 
vector<int> solution(int m, int n, vector<vector<int>> picture)
{
    max_size_of_one_area = 0;
 
    visit = vector<vector<bool>>(m, vector<bool>(n, false));
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (picture[i][j] != 0 && !visit[i][j])
            {
                BFS(picture[i][j], dx, dy, picture, m, n, i, j);
                count++;
            }
        }
    }
 
    vector<int> answer(2);
    answer[0] = count;
    answer[1] = max_size_of_one_area;
    return answer;
}

---