📒활용개념

DFS를 이용하여 모든 부분을 체크하며 탐색한다.
QUEUE의 활용.

📌문제설명

• 문제
  출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

• 조건
  - 1 <= m, n <= 100
  - picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
  - picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.
  

📌구현

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

using namespace std;

//방문 여부 확인 변수
bool check[100][100];

int l[4] = {0,0,1,-1};
int c[4] = {1,-1,0,0};

//방문하지 않은 부분부터 주변의 방문 여부와 색 일치 여부 확인 DFS함수
int dfs(int low, int col, int color,vector<vector<int>> pic){
    queue<pair<int, int>> qu;
    qu.push({low, col});
    
    int num = 1;
    
    check[low][col] = true;
    
    while(!qu.empty()){
        pair<int, int> tmp = qu.front();
        qu.pop();
        
        for(int i=0; i<4; i++){
            int now_l = tmp.first + l[i];
            int now_c = tmp.second + c[i];
            
            if(now_l>=0 && now_l<pic.size()&& now_c>=0 && now_c<pic[0].size()){
                if(!check[now_l][now_c] && color==pic[now_l][now_c]){
                    qu.push({now_l, now_c});
                    check[now_l][now_c]=true;
                    num++;
                }
            }
        }
    }
    return num;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size= 0;
    int size;
    
    vector<int> answer(2);
    
    //전역변수 초기화
     for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            check[i][j]=false;
        }
    }
    
    //방문하지 않은 행렬에 대한 방문과 영역 개수 확인
    for(int i=0; i<m; i++){
        for(int j =0; j<n; j++){
            int color = picture[i][j];
            if(color>0 && !check[i][j]){
                size=dfs(i, j, color, picture);
                number_of_area++;
            }
        }
        if(max_size<size){
            max_size = size;
        }
    }
    
    answer[0] = number_of_area;
    answer[1] = max_size;
    return answer;
}

📌주의점

• 문제에서 전역변수 사용시 초기화를 하라는 조건이 있었는데 그 조건을 만족하지 못해서 처음에 테스트 케이스만 맞고 채점시 반복적으로 틀리는 상황이 발생했다. 아무리 봐도 코드에 문제가 없는 것 같아서 답답해서 문제의 질문하기를 찾아봤다. 질문하기 상황에 생각보다 나와 같은 이유로 문제를 통과하지 못하는 사람이 많이 있었다. 문제의 조건을 만족시키는 것이 중요하다는 생각이 들었던 문제다.
• m과 n이 어떤 것을 의미하는지 처음에 잘 이해하지 못하여 모든 것을 .size를 사용하여 문제를 풀었었다. 하지만 문제를 리뷰하는 과정에서 그 의미를 이해하였고, 코드를 일부 수정하였다. 행과 열의 위치와 의미를 파악하는 것이 중요했던 문제다.