[프로그래머스] 코딩테스트 연습 2017 카카오코드 예선 카카오프렌즈 컬러링북 with C++

안녕하세요! 오늘은 프로그래머스 카카오프렌즈 컬러링북 문제를 풀어보았습니다!

2레벨은 문제가 몇개 안되 C++문제도 같이 풀려고합니다!

 

Swift로 풀어보고 싶었으나 어쩔 수 없죠 ㅠ

 

이 문제는 기본적인 탐색 문제입니다!

 

bfs(Breadth First Search)나 dfs(Depth First Search) 중 사용하면 되는데요!

 

서로 장단점이 있는 알고리즘입니다! 나중에 포스팅으로 dfs와 bfs에 대해 자세히 포스팅 하도록하겠습니다!

 

저는 dfs로 문제를 풀었는데요!

 

같이한번 살펴보시죠!

 

 

우선 인자로 들어온 vector<vector<int>> picture 를 함수 내부에서 사용하기 좋게 전역변수로 선언한 map으로 옮겨줍니다!

 

옮겨주면서 isVisitedMap도 같이 초기화해줍니다!

    for(int i = 0; i < m; i++){
        for(int j =0; j < n; j++){
            if (picture[i][j] == 0)
                isVisitedMap[i][j] = 1;
            else
                isVisitedMap[i][j] = 0;
            map[i][j] = picture[i][j];
        }
    }

색이 없으면(값이 0이면) 어처피 방문하지 않을것이기에 isVisitedMap에 1(true)을 넣어줍니다!

 

그리고 맵 전체를 탐색하는 dfs알고리즘을 구현합니다!

void dfs(int m, int n, int color){
    isVisitedMap[m][n] = 1;
    count++;
    
    for(int i = 0; i < 4; i++){
        int newM = m + priorityDirection[i][0];
        int newN = n + priorityDirection[i][1];
        if (isVisitedMap[newM][newN] == 0 && map[newM][newN] == color) {
            isVisitedMap[newM][newN] = 1;
            dfs(newM, newN, color);
        }
    }
}

dfs는 재귀형식으로 program counter에 의해 스택 자료구조를 이용하게 되는데요! 흠... 이부분도 나중에 컴퓨터 구조에 추가하여 올려드리도록 하겠습니다!

 

우선순위를 정하고 정한방향으로 가면서 조건에 맞는(같은색인) 곳을 탐색하고 isVisitedMap에 기록합니다.

 

이렇게 dfs알고리즘을 이용해 순회 하면서 number_of_area와 max_size_of_one_area를 기록해주시면 쉽게 문제를 해결하실 수 있습니다!

 

 

#include <vector>

using namespace std;

int isVisitedMap[101][101] = {0,};
int map[101][101]= {0,};
int priorityDirection[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int count = 0;

void dfs(int m, int n, int color){
    isVisitedMap[m][n] = 1;
    count++;
    
    for(int i = 0; i < 4; i++){
        int newM = m + priorityDirection[i][0];
        int newN = n + priorityDirection[i][1];
        if (isVisitedMap[newM][newN] == 0 && map[newM][newN] == color) {
            isVisitedMap[newM][newN] = 1;
            dfs(newM, newN, color);
        }
    }
}

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)
                isVisitedMap[i][j] = 1;
            else
                isVisitedMap[i][j] = 0;
            map[i][j] = picture[i][j];
        }
    }
    
    for(int i = 0; i < m; i++){
        for(int j =0; j < n; j++){
            if (isVisitedMap[i][j] == 0 && map[i][j] != 0) {
                number_of_area++;
                count = 0;
                dfs(i, j, map[i][j]);
                if (count > max_size_of_one_area) {
                    max_size_of_one_area = count;
                }
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

 

오늘은 여기까지 입니다!

 

좋은 하루 되세요!