[Programmers]프로그래머스 카카오프렌즈 컬러링북(c++)

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

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

 

코딩테스트 연습 > 2017 카카오코드 예선 > 카카오프렌즈 컬러링북

 

1. DFS로 상,하,좌,우 중 같은 숫자가 있다면 area의 key값에 해당하는 area[cnt]영역을 +1 해준다

2. 방문한 곳은 isVisited = true로 설정해줘서, 재방문하지 않게 한다.

3. 해당 cnt의 DFS가 한번 끝날때마다 max_size_of_one_area의 최댓값을 갱신해준다. (area[cnt]중 가장 큰 값으로 갱신)

3. DFS가 종료되면, area의 사이즈를 number_of_area변수에 저장한다. 

 

 

---

main포함 코드(c++)

 

#include <vector>
#include <unordered_map>
using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int number_of_area = 0;
int max_size_of_one_area = 0;
int cnt = 0;
void DFS(int m,int n,vector<vector<int>> picture, int x, int y, vector<vector<bool>> &isVisited, unordered_map<int, int> &area){
    
    if(isVisited[x][y]) return;
    isVisited[x][y] = true;
    area[cnt]++;
    
    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < m&& ny < n && nx >= 0 && ny >= 0 && picture[nx][ny] == picture[x][y])
            DFS(m, n, picture, nx, ny, isVisited, area);
        
    }
    
    max_size_of_one_area = max(area[cnt], max_size_of_one_area);
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<vector<bool>> isVisited(m, vector<bool>(n,0));
    vector<int> answer(2);
    unordered_map<int, int> area;
    dx[0] = 0, dx[1] = 0, dx[2] = -1, dx[3] = 1;
    dy[0] = -1, dy[1] = 1, dy[2] = 0, dy[3] = 0;
    number_of_area = 0;
    max_size_of_one_area = 0;
    cnt = 0;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!isVisited[i][j] && picture[i][j] != 0) {DFS(m,n,picture, i, j, isVisited, area); cnt++;}
        }
    }

    number_of_area = area.size();
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    
    return answer;
}



 

 

---

테스트케이스는 통과가 되는데, 채점하니까 테스트케이스가 총1개인데 답이 틀렸다고 나와서, 뭐가 문제인지 질문하기 게시판을 봤더니.. 전역변수는 solution함수에서 초기화를 시켜줘야 했었다. 그래서

dx[0] = 0, dx[1] = 0, dx[2] = -1, dx[3] = 1;
dy[0] = -1, dy[1] = 1, dy[2] = 0, dy[3] = 0;
number_of_area = 0;
max_size_of_one_area = 0;
cnt = 0;

해당 코드를 solution에서 추가시켜줬더니 잘 해결됐다.