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

Drakk·2021년 7월 25일

C 알고리즘 예선 카카오코드 카카오프렌즈 컬러링북

알고리즘 문제풀이

목록 보기

13/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.
* 1 <= m, n <= 100
* picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
* picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

🧺출력
리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

🔋예제 입출력

🔮예제 입력

🔮예제 출력

💉문제 분석

🔋분류

bfs, dfs, 그래프이론, 브루트포스

🔋난이도

(solved.ac기준) 실버I~골드IV

💉문제 풀이

🔋해법

저는 개인적으로 bfs로 풀었습니다.
매우 쉬운문제입니다.

그냥 일반적인 bfs문제라서 크게 설명할것은없지만,
저는 브루트포스로 모든 점을 순회하면서, 만약에 그 점이 방문하지않은점이면서 0이아니라면 그 점에 대하여 bfs를 수행하도록했습니다.

🔋소스코드

#include <vector>
#include <utility>
#include <queue>

constexpr int MAX = 101;

std::vector<int> solution(int m, int n, std::vector<std::vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    const int dx[4] = { 0, 0, 1, -1 };
    const int dy[4] = { 1, -1, 0, 0 };

    bool visit[MAX][MAX] = { false, };

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(!visit[i][j] && picture[i][j] != 0) {
                ++number_of_area;
                std::queue<std::pair<int, int>> q;
                q.push({ i, j });
                visit[i][j] = true;
                int result = 1;

                while(!q.empty()){
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();

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

                        if(ny >= 0 && nx >= 0 && ny < n && nx < m){
                            if(!visit[ny][nx] && picture[ny][nx] == picture[y][x]){
                                visit[ny][nx] = true;
                                q.push({ ny, nx });
                                ++result;
                            }
                        }
                    }
                }
                max_size_of_one_area = std::max(result, max_size_of_one_area);
            }
        }
    }t

    std::vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}