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

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

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

---

 문제 풀이

기본적인 BFS 문제이다.

BFS에 최대 범위와 map 그리고 시작 좌표를 입력받고 target 값과 같은 값을 찾는다.

target 값과 같다면 해당 영역의 사이즈를 늘려주고 return 해주면 된다.

 

BFS에는 방문 여부가 필수이므로 memset을 통해서 vistied의 값을 초기화해준다.

 느낀 점

백준에서 풀었던 아기 상어 문제가 많이 도움이 되었다. 백준과 약간 다른 형식으로 처음에 살짝 버벅거렸지만 금방 해결하였다. BFS 문제를 좀 더 풀어봐야 할 것 같다.

 코드

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

using namespace std;

int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
bool visited[101][1001];

int BFS(int m, int n, int x, int y, vector<vector<int>> picture) {
    visited[x][y] = true;
    int size = 1;
    int target = picture[x][y];
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));

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

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

            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (!visited[nx][ny] && picture[nx][ny] == target) {
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                    size++;
                }
            }
        }
    }
    return size;
}

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

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n;j++) {
            if (!visited[i][j] && picture[i][j] != 0) {
                int size = BFS(m, n, i, j, picture);
                max_size_of_one_area = max(size, max_size_of_one_area);
                number_of_area++;
            }
        }
    }

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