[programmers] Lv.2 카카오프렌즈 컬러링북(c++)

#include <vector>
#include <queue>

using namespace std;

vector<vector<bool>> visit;
int nb_area;
vector<int> x_dir;
vector<int> y_dir;

int find_area(int i, int j, vector<vector<int>> picture){
    nb_area++;
    
    queue<pair<int,int>> que;
    que.push({i, j});
    visit[i][j] = true;
    int cnt = 0;
    while(!que.empty()){
        auto[x, y] = que.front(); que.pop();
        cnt++;
        
        for (int k = 0; k < 4; k++) {
            if (x + x_dir[k] >= 0 && x + x_dir[k] < picture.size()
            	&& y + y_dir[k] >= 0 && y + y_dir[k] < picture[0].size()
                && picture[x][y] == picture[x + x_dir[k]][y + y_dir[k]] 
                && visit[x+x_dir[k]][y+y_dir[k]] == false) {
                	que.push({ x + x_dir[k], y + y_dir[k] });
                	visit[x + x_dir[k]][y + y_dir[k]] = true;
            }
        }
    }
    
    return cnt;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    nb_area = 0;
    int max = 0;
    
    x_dir = {-1, 1, 0, 0};
    y_dir = {0, 0, -1, 1};
    
    visit = vector<vector<bool>>(m, vector<bool>(n, false));
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(picture[i][j] != 0 && visit[i][j] == false){
                int temp = find_area(i, j, picture);
                if(temp > max) max = temp;
            }
        }
    }
    
    return {nb_area, max};
}

---

문제

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

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

728x90

 

테스트 케이스가 너무 적어서 문제를 참고하여 두가지 더 추가하였다.

하지만 아래를 만족해도 틀릴 수 있다.

6, 4, [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] : 정답 [4, 5]

13, 16, [[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0], [0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0], [0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0], [0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]] : 정답 [12, 120]

---

[접근]

BFS로 해당 색의 영역을 돌면서 해당 영역의 넓이를 카운트한다.

들른곳을 true로 표시하고 전체 영역을 돌면서 false이면서 색이 있는곳을 bfs로 넣어주면

bfs가 call된 횟수가 곧 영역의 개수가 된다.

 

BFS

https://jolly-note.tistory.com/63

BFS (Breadth First Search, 너비 우선 탐색)