[프로그래머스] 카카오프렌즈 컬러링북

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1829

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

 

그림이 주어졌을 때, 상하좌우가 같은 색깔인 경우 '이어져 있다'고 부릅니다.

이어져 있는 영역의 개수를 구하고, 그 중 가장 넓이가 큰 영역의 넓이를 구하는 문제입니다.

단, 색깔이 0인 경우에는 그림이 아닌 것으로 판단하여 넓이의 갯수 및 크기에 합산하지 않습니다.

 

같은 색이 어디까지 이어져 있는지 확인하려면 탐색을 해야 하므로, 탐색 알고리즘을 사용했습니다.

구현이 상대적으로 간편한 BFS를 사용하였고, 각 칸의 방문 여부를 visited 배열을 사용해 기록 및 활용하였습니다.

bfs는 별도 함수로 분리하여 사용하였습니다.

 

이 문제도 전 문제와 마찬가지로 (옛날 문제라서 그런지) 전역변수를 사용하면 테스트 케이스는 통과하는데 채점 케이스는 에러가 나는 문제가 있어서,

visited, dx, dy 등 다양한 배열을 전부 함수 안에 작성하여 동적으로 생성되도록 하였습니다.

 

코드 링크: GitHub

GitHub - kchung1995/code_test_personal: 혼자 코딩 테스트 공부를 하며 사용하는 저장소

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1829
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int bfs (int m, int n, int x, int y, vector<vector<bool> > &visited, vector<vector<int> > &picture) {
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int currentColor = picture[x][y];
    
    int answer = 1;
    queue<pair<int, int> > q;
    visited[x][y] = true;
    q.push({x, y});
    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];

            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (picture[nx][ny] != currentColor) continue;
            if (visited[nx][ny] == true) continue;
            visited[nx][ny] = true;
            answer++;
            q.push({nx, ny});
        }
    }
    return answer;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    vector<int> answer;
    vector<vector<bool> > visited;
    
    // 방문 배열 초기화
    vector<bool> visited_entry;
    for (int j = 0; j < n; j++) {
        visited_entry.push_back(false);
    }
    for (int i = 0; i < m; i++) {
        visited.push_back(visited_entry);
    }
    
    // 방문하지 않은 칸을 찾아다님
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 방문하지 않은 경우
            if (!visited[i][j]) {
                int area_size = bfs(m, n, i, j, visited, picture);
                if (picture[i][j] != 0) {
                    number_of_area++;
                    max_size_of_one_area = max(max_size_of_one_area, area_size);
                }
            }
        }
    }
    
    // 반환할 답 정리
    answer.push_back(number_of_area);
    answer.push_back(max_size_of_one_area);
    return answer;
}

 

문제 관련 질문이 있으시면 언제든 댓글 달아주세요.