title: "[프로그래머스] 카카오프렌즈 컬러링북 C++ 해설 (Level 2) - 이도훈"
cleanUrl: "programmers/1829"
description: "프로그래머스 Level 2 문제 [카카오프렌즈 컬러링북]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

• BFS를 활용한 플러드 필 문제입니다.
• 이 문제 채점 시스템 특성 상 bool vis[101][101] = {false} 처럼 명시적으로 값을 초기화해주어야 통과합니다.

코드

#include <vector>
#include <queue>

using namespace std;

int bfs(int r, int c, vector<vector<int>> picture, bool vis[101][101], int R, int C) {
    int dr[4] = {1, 0, -1, 0};
	int dc[4] = {0, 1, 0, -1};
    queue<pair<int, int>> q;
    int size = 0;
    
    q.push({r, c});
    vis[r][c] = 1;
    int color = picture[r][c];
    
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        size++;
        
        for (int i = 0; i < 4; i++) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];
            
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (vis[nr][nc] || picture[nr][nc] != color) continue;
            
            q.push({nr, nc});
            vis[nr][nc] = 1;
        }
    }
    
    return size;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    bool vis[101][101] = {false};
    
    for (int r=0; r < m; r++) {
        for (int c=0; c < n; c++) {
            if (vis[r][c] || picture[r][c] == 0) continue;
            
            number_of_area++;
            int size = bfs(r, c, picture, vis, m, n);
            if (size > max_size_of_one_area) {
                max_size_of_one_area = size;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges