카카오프렌즈 컬러링북 (c++)

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

프로그래머스

: 전체를 탐색해야하기 때문에 DFS 나 BFS로 풀이하면 됨. 

 

DFS와 BFS의 차이는

DFS는 stack으로 구현, BFS는 queue로 구현이라고 생각하면 기억하기 좋다.

 

재귀함수로 구현하는게 편할 것 같아서 재귀함수로 구현 -> DFS 

 

[문제풀이]

#include <vector>

using namespace std;

bool check[100][100]; // 영역 재탐색 방지를 위한 배열 
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void findArea(const int m, const int n, const int x, const int y, int& area, const vector<vector<int>> picture){
    if(check[x][y]) return;

    check[x][y]=true; // 방문    
    area++; // 영역 확장
    int color = picture[x][y]; // 현재 영역 색상
    
    for(int i=0;i<4;i++){ // 상하좌우 탐색
        int tx = x+dx[i];
        int ty = y+dy[i]; 
        
        if(tx>=0&&tx<m&&ty>=0&&ty<n&&picture[tx][ty]==color){ // 범위 내 && 같은 영역(색상)인 경우 
            findArea(m,n,tx,ty,area,picture);
        }
        
    }
    
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    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(picture[i][j]==0) // 0인 경우 탐색 안함 
                check[i][j]=true;
            else check[i][j]=false;
        }
    }
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!check[i][j]){
                number_of_area++; // 새로운 영역 탐색
                int area = 0;
                findArea(m, n, i, j, area, picture);
                max_size_of_one_area = (max_size_of_one_area < area)? area:max_size_of_one_area; // 가장 큰 영역의 넓이 update
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

bool check[100][100]	방문(영역에 포함)된 경우 다시 방문하지 않기 위해 확인하는 배열
int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1};	상하좌우 탐색 시 코드를 더 간단히하기 위해 사용되는 배열  -> 조건문 4개가 아니라 반복문 하나로 코드를 구현할 수 있다
void findArea(const int m, const int n, const int x, const int y, int& area, const vector<vector<int>> picture)	영역 탐색을 위해 사용되는 함수. - 변하면 안되는 변수는 const 사용 - area : 현재 영역의 크기  - 이 함수가 불려졌다는 것은 방문 + 영역 확장의 의미가 있음 따라서, 이에 해당하는 check 배열과 area 변수 값을 재설정

 

[comment]

처음에, 상하좌우를 모두 방문하는 방법 말고 특정 조건에서는 어떤 방향만 방문하고(예를 들어서, 우로 확장된 경우에는 좌는 검사를 안한다던지..) 하는 방법도 고려해봤는데, 그런 문제가 아니었고.. 생각해보니 어차피 방문 check하는데 시간에 큰 영향을 안 미치겠다는 생각이 들었다.. 그냥 전체탐색하는 문제였다.. ㅎㅎ간단한 문제이지만 dx[4], dy[4] 로 코드 깔끔하게하는 법은 배운듯하다