[2017 카카오 코드 예선] 카카오 프렌즈 컬러링북

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

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

 

#include <vector>
#include <queue>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    bool visit[101][101] = {0,};
    int dc[4] = {1,-1,0,0};
    int dr[4] = {0,0,1,-1};
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    vector<int> answer(2);

    queue<pair<int,int> > q;

    for(int c=0;c<m;c++) {
        for(int r=0;r<n;r++) {
            int originalColor = picture[c][r];
            int size_of_one_area = 1;

            if(originalColor==0 || visit[c][r]) {
                continue;
            }

            visit[c][r] = true;
            q.push({c,r});

            while(!q.empty()) {
                int col = q.front().first;
                int row = q.front().second;
                q.pop();

                for(int i=0; i<4; i++) {
                    int nc = col + dc[i];
                    int nr = row + dr[i];

                    if(nc>=m || nc<0 || nr>=n || nr<0 || visit[nc][nr]) {
                        continue;
                    }

                    if(picture[nc][nr] == originalColor) {
                        visit[nc][nr] = true;
                        size_of_one_area += 1;
                        q.push({nc,nr});
                    }
                }
            }

            number_of_area+=1;
            max_size_of_one_area = max_size_of_one_area > size_of_one_area ? max_size_of_one_area : size_of_one_area;
        }
    }
    
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;

    return answer;
}

 

2중 반복문을 돌면서 모든 행,열에 대해 BFS 완전탐색하면 된다.

 

이 때 dc[], dr[], visit[] 과 같은 배열들을 전역으로 선언했더니

테스트 케이스는 통과하고 제출시 실패하는 문제가 있었다.

전부 solution() 내에 선언하니 해결되었다.