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

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

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

 

 

 

알고리즘 종류

    - BFS

 

 

사고 과정

    1. 2중 for문으로 picture를 탐색한다.

        1-1. 이미 방문했거나 색이 칠해지지 않았으면 탐색하지 않는다.

    2. 탐색할 위치의 y와 x를 찾았으면, BFS를 수행한다.

        2-1. 이동할 때 가용한 범위에 있는지 확인한다.

        2-2. 같은 색인지 확인한다.

        2-3. 이미 방문했는지 확인한다.

    3. BFS 탐색이 끝났으면, 최대 영역의 값을 갱신한다.

 

 

 

구현(C++)

#include <vector>
#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int N, M;
int isVisited[101][101];
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (x>=0 && x<N) && (y>=0 && y <M);
}
 
int bfs(int y, int x, vector<vector<int>> picture){
    queue<pair<int, int>> q;
    q.push({y,x});
    isVisited[y][x] = 1;
    int color = picture[y][x]; // 탐색할 색 초기화
    int cnt = 1; // 탐색할 색의 개수 초기화
    
    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            
            // BFS 이동 조건들
            if(isVisited[ny][nx]) continue;
            if(!isValid(ny, nx)) continue;
            if(picture[ny][nx] != color) continue;
            
            isVisited[ny][nx] = 1;
            cnt ++;
            q.push({ny, nx});
            
        }
    }
    return cnt;
}
 
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    
    // 초기화
    memset(isVisited, 0, sizeof(isVisited));
    N = n; M = m;
    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(isVisited[i][j]) continue;
            if(picture[i][j] == 0) continue;
            
            number_of_area ++; // 영역 개수 
            max_size_of_one_area = max(bfs(i, j, picture), max_size_of_one_area); // 최대 넓이 영역 탐색
        }
    }
 
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    
    return answer;
}

 

 

 

시행착오