[알고리즘문제] 프로그래머스 - 카카오프렌즈 컬러링북도움말

처음에 문제를 읽고 이게 무슨 말이지...생각을 했었는데 그냥 탐색문제였다.

구역의 수 / 한 구역의 최대크기를 구하는 문제이다. 여기서 구역은 상하좌우로 이어진 공간을 뜻한다.

 

1 1  1  0          

1 2 2 0

1 0 0 1

0 0 0 1

0 0 0 3

0 0 0 3

예제를 보면 다음과 같은 행렬이 있을 때,

 

1 1 1 1            2 2                    1                3

1                                            1                3

                                              1

0을 제외하고 총 4개의 구역을 얻을 수 있다.

여기서 하나의 구역에서 크기가 가장 큰 경우는 첫번째 1이 5개인 경우이며, 4와 5를 return하면 된다.

 

처음에 문제를 이해했을 때 dfs로 풀면 되겠지 생각을 했고, 풀었는데 testcase는 합격했는데 정답제출을 하면 틀렸다고 나왔다. 그래서 바로 bfs로 풀어봤는데, 맞다고 나왔었다. 오랜만에 dfs, bfs로 문제를 풀어봤는데 아직 기억하고 있었다..신기하다



1.dfs

#include <vector>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

// 우,하,좌,상
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};


int depth=0;
int width;
int height;
int check[101][101] = { 0, };

void dfs(int y,int x,int n,vector<vector<int>> picture){
    if(check[y][x]){
        return;
    }
    depth++;
    check[y][x]=1;
    
    for(int i=0;i<4;i++){
        
        int newY = y + dy[i];
        int newX = x + dx[i];
        
        if(newY < height && newY >=0 && newX < width && newX >=0){
            if(!check[newY][newX] && picture[newY][newX]==n){
                dfs(newY,newX,n,picture);
            }
        }
    }
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {

    int number_of_area = 0;
    int max_size_of_one_area = 0;
        
    height = m;
    width = n;
    
    
    for(int y=0;y<picture.size();y++){
        for(int x=0;x<picture[y].size();x++){
            if(!check[y][x] && picture[y][x] > 0){ // 방문안하고, 0보다 큰 곳만 탐색
                number_of_area++;
                dfs(y,x,picture[y][x],picture);
                max_size_of_one_area = max(max_size_of_one_area,depth);
                depth=0;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

2.bfs

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

// 우,하,좌,상
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};


vector<int> solution(int m, int n, vector<vector<int>> picture) {

    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    queue<pair<int,int>> que;
    
    int visited[101][101] = { 0, };
    
    
    for(int y=0;y<picture.size();y++){
        for(int x=0;x<picture[y].size();x++){
            if(picture[y][x] > 0 && !visited[y][x]){
                
                int currentNum = picture[y][x];
                int depth=0;
                
                que.push(make_pair(y,x));
                
                while(!que.empty()){
                    
                    int y = que.front().first;
                    int x = que.front().second;
                    que.pop();
                    
                    for(int i=0;i<4;i++){
                        
                        int newY = y + dy[i];
                        int newX = x + dx[i];
                        
                        if(newY < m && newY >=0 && newX < n && newX >=0){
                            if(picture[newY][newX] == currentNum && !visited[newY][newX]){
                                que.push(make_pair(newY,newX));
                                depth++;
                                visited[newY][newX]=1;
                            }
                        }
                    }
                }
                max_size_of_one_area = max(max_size_of_one_area,depth);
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}