프로그래머스 2단계 - 카카오프렌즈 컬러링북

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

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

- 문제파악

이중배열에서 상하좌우로 연결된 요소들은 같은 영역에 있다고 판단한다. 요소의 숫자가 다르면 상하좌우에 연결되어 있어도 다른 영역이라고 판단한다. 이 때, 영역의 개수와 영역들 중 가장 넓은 너비 값을 출력하라.

 

- 정답

BFS로 문제를 해결했다.

계속 실패하길래 주석을 읽어보니 전역변수를 꼭 solution 함수 내에서 초기화 해야한다...

 

#include "bits/stdc++.h"

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.

vector<unsigned int> solution(int m, int n, vector<vector<int>> picture) {
    unsigned int number_of_area = 0;
    unsigned int max_size_of_one_area = 0;
    
    vector<unsigned int> answer(2);

    int arr[101][101] = {0,};
    queue<pair<int,int>> q;
    
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(picture[i][j] && !arr[i][j])
            {
                int num = picture[i][j];
                unsigned int nCnt = 0;
                number_of_area++;
                q.push({i,j});
                arr[i][j] = 1;
                
                while(!q.empty())
                {
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    nCnt++;
                    
                    for(int k = 0 ; k < 4 ; k++)
                    {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        if(nx < 0 || nx >= n) continue;
                        if(ny < 0 || ny >= m) continue;
                        if(!picture[ny][nx]) continue;
                        if(num != picture[ny][nx]) continue;
                        if(arr[ny][nx]) continue;
                        
                        arr[ny][nx] = 1;
                        q.push({ny,nx});
                        
                    }               
                }
                max_size_of_one_area = max(nCnt,max_size_of_one_area);
            }
        }
    }
    
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    
    
    return answer;
}