프로그래머스 레벨3 카카오 프렌즈 컬러링북

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

 

풀이

DFS를 이용.

picture의 모든칸에 방문하지 않았거나 값이 0이 아니면 DFS를 실행한다. 

DFS를 한번 실행할때마다 하나의 영역이 만들어지고, DFS를 실행한 횟수가 영역의 개수다.

 

영역을 만들기 위해 실행한 DFS는

방문하지 않았고 현재 칸의 값과 같은 값을 가지는 칸을 상하좌우로 방문해서 방문처리하는것을 반복한다.

그리고 방문할때마다 cnt변수값을 1증가시켜서 최종적으로 리턴할때 cnt값이 이번 DFS의 max_size_of_one_area가 된다.

영역이 만들어질때마다 기존 max_size_of_one_area과 비교해서 큰값으로 갱신한다.

 

---

구현

//c++

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;


void dfs(int m, int n, int y, int x, vector<vector<int>> &v, int &cnt, int visited[][101], int dy[], int dx[]){
    visited[y][x] = 1;
    for(int i=0;i<4;i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny>=0 && nx>=0 && ny<m && nx<n && visited[ny][nx] == 0 && v[ny][nx] == v[y][x]){
            dfs(m, n, ny, nx, v, cnt, visited, dy, dx);
        }
    }
    cnt++;
    return;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    int visited[101][101];
    int dy[4] = {-1,1,0,0};
    int dx[4] = {0,0,-1,1};
    
    memset(visited, 0, sizeof(visited));
    
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j] == 0 && picture[i][j] > 0) {
                int cnt = 0;
                dfs(m, n, i, j, picture, cnt, visited, dy, dx);
                cout<<cnt<<endl;
                max_size_of_one_area = max(max_size_of_one_area, cnt);
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}