카카오프렌즈 컬러링북 (프로그래머스) - C++

 

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

 

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

• 설명
  • 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.
    • 1 <= m, n <= 100
    • picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
    • picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.
  • 영역의 연결은 가로, 세로만 포함된다.(대각선은 연결된 영역이 아니다.)
• 풀이
  • BFS를 사용하여 4방향(상하좌우)를 방문하여 같은 값인지를 판단한다.
  • 모든 경로를 탐색한 후 0이 아닌 값이면 리턴 값을 수정해준다.

#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//4방향 체크
    bool visited[101][101] = {0,};//방문했는지를 확인
    
    //왼쪽 위에서 시작한다.
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(!visited[i][j])//방문하지 않았다면
            {
                queue<pair<int,int>> q;
                q.push(make_pair(i,j));//해당 인덱스부터 탐색시작
                visited[i][j] = true;
                
                int val = picture[i][j];
                int count = 1;
                
                //BFS
                while(!q.empty())
                {
                    pair<int,int> cur = q.front();
                    
                    q.pop();
                    
                    for(int i = 0 ; i < 4 ; i++)//4방향 체크
                    {
                        int x = cur.first + direction[i][0];
                        int y = cur.second + direction[i][1];
                        
                        if(x <0 || y <0 || x >= m || y >= n)//인덱스 예외처리
                        {
                            continue;
                        }
                        
                        if(!visited[x][y] && val == picture[x][y])//방문하지 않았고, 같은 값이라면
                        {
                            //cout << picture[x][y] <<"  "<< x <<","<< y << " " << endl;
                            q.push(make_pair(x,y));
                            visited[x][y] = true;
                            count++;
                        }
                    }
                }
                
                //cout << count << endl;
                if(val != 0)//비어있는 공간이 아닐경우 답을 갱신해준다.
                {
                    number_of_area++;
                    max_size_of_one_area = max(max_size_of_one_area,count);
                }
                    
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}