[2017 카카오코드 예선] 카카오 프렌즈 컬러링북

문제

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

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

문제설명

이 문제의 핵심질문은 그림판에 색칠된 영역들을 구할 수 있냐? 구분할 수 있냐? 로 정리할 수 있다.

"영역의 크기"를 구하기 위해선 우리가 알고 있는 방법은 당연 DFS, BFS 이다.

DFS, BFS 관련된 문제와 설명들은 구글링을 통해서 쉽게 접할 수 있을 것이다.

 

우선 모든 picture의 위치(i, j)에 접근하여 해당 위치가 영역체크를 하였는지에 대해 visited 배열에 저장을 하였다.

영역체크가 되어있지 않으면 BFS를 통해 해당영역의 크기를 구하고 영역의 개수를 늘려가는 방식으로 진행하였다.

 

코드

#include <vector>
#include <algorithm>
#include <queue>
#define MAX		101
using namespace std;

bool visited[MAX][MAX];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            visited[i][j] = false;
        }
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int area = 0;
            int color = picture[i][j];
            if (!visited[i][j] && color != 0)
            {
                visited[i][j] = true;
                number_of_area++;

                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                area++;
                
                while (!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();

                    for (int k = 0; k < 4; k++)
                    {
                        int nx = x + dx[k];
                        int ny = y + dy[k];

                        if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                            continue;

                        if (!visited[nx][ny] && picture[nx][ny] == color)
                        {
                            visited[nx][ny] = true;
                            q.push(make_pair(nx, ny));
                            area++;
                        }
                    }
                }
            }

            max_size_of_one_area = max(max_size_of_one_area, area);
        }
    }   
		
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}