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

해결방법

• 몇 개의 영역이 있는지 👉 DFS 여러번 돌리기
• 가장 큰 영역의 넓이 👉 ???

가장 큰 영역의 넓이 구하기

먼저 생각했던건 dfs안에 크기를 계속 갖고있으면서.. 전달하는것
근데 이렇게되면 깊어질수록 숫자가 커지고 다시 위로 돌아오면 사라진다 ㅜㅜ

그래서 위 그림과 같이 풀고자 했다.

• 일단 dfs실행 시 기본적으로 cnt = 1을 가지고 있다
• 그 안에서 dfs 실행했을 때 돌아오는 값을 cnt에 더해준다
  • 범위를 벗어나거나, 다른영역이거나, 방문한 적 있다면
    더해주는 과정 없이 continue할 것이므로 1을 리턴하게됨
• cnt를 리턴한다

전역변수 초기화

ㅋㅋ
실행했을땐 맞고 제출했을땐 틀리길래 오열할뻔
https://school.programmers.co.kr/questions/34062
solution 함수 내에서 전역변수 초기화를 해주지 않으면 제출했을 때 틀린다.
꼭 기억하자....... 전역변수 .... 초기화 ......

소스코드

#include <vector>
#include <iostream>
using namespace std;
#define pii pair<int, int>


bool visited[101][101];
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
int M,N;

int dfs(vector<vector<int>>& pic, pii start){
    int x = start.first; int y = start.second;
    
    int cur = pic[x][y];
    visited[x][y] = true;
    int cnt = 1;
    for(int i = 0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx<0 || nx>=M || ny<0 || ny>=N) continue;
        if(visited[nx][ny] || cur != pic[nx][ny]) continue;
        cnt += dfs(pic,{nx,ny});
    }
    return cnt;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    M = m; N = n;
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            visited[i][j] = false;
        }
    }
    
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(!picture[i][j] || visited[i][j]) continue;
            max_size_of_one_area = max(max_size_of_one_area,dfs(picture,{i,j}));
            number_of_area++;
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

아직도 재귀는 힘드렁