[프로그래머스] 2017 카카오코드 예선 - 카카오프렌즈 컬러링북, C++

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

코딩테스트 연습 - 카카오프렌즈 컬러링북 | 프로그래머스

 본 문제는 2017 카카오코드 예선 문제다. bfs, dfs로 문제를 해결할 수 있다. 개인적으로 x, y를 이용하여 다음 영역으로 찾아가는 문제는 queue를 이용한 bfs 풀이가 편하기 때문에 bfs로 풀었다. 코딩하기 편한 방법으로 하는 것이 주어진 시간 내에 문제를 정확히 풀어야 하는 기업 코딩테스트에 가장 좋은 방법이라고 생각한다.

이 문제는 TC가 1개라 좋은 문제는 아닌거 같다.

1. 색칠하지 않은 영역을 0이라고 하였으니 0이 아닌 원소를 찾는다.
2. 0이 아닌 원소를 찾았으면 상하좌우로 동일한 원소를 탐색한다.
3. 동일한 원소를 모두 찾았으면 원소의 개수를 최대값과 비교한다.
4. 1번을 반복하여 모든 영역을 찾는다.
5. 영역의 개수와 최대 영역의 개수를 return 한다.

#include <vector>
#include <queue>
 
using namespace std;
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    bool chk[100][100] = {0};
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    queue<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (picture[i][j] == 0 || chk[i][j]) continue; // 0이거나 방문한 원소 제외
            number_of_area += 1; // 영역의 개수
            int cnt = 1;
            int tmp = picture[i][j];
            q.push(make_pair(i, j));
            chk[i][j] = true;
            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 (!chk[nx][ny] && picture[nx][ny] == tmp) { 
                            chk[nx][ny] = true;
                            q.push(make_pair(nx, ny));
                            cnt += 1;
                        }
                    }
                }
            }
            // 최대 원소 개수 비교
            if (max_size_of_one_area < cnt) max_size_of_one_area = cnt;
        }
    } 
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}