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

프로그래머스

 

 

• 단순한 bfs 문제
• 연결된 같은 색상으로 이루어진 영역의 개수와, 가장 넓은 영역의 넓이를 구하는 문제

> 정답률이 낮아서 좀 난이도가 있는 문제인가 싶었는데 열어보니 그냥 bfs로 해결하면 되는 문제였다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};
bool visited[101][101];

//bfs
int bfs(int i, int j, int m, int n, vector<vector<int>> picture) {
    int color = picture[i][j];
    int size = 1;
    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;
    
    while(!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        
        // 4방향으로 이동
        for(int i = 0; i < 4; i++) {
            int nx = curX + dirX[i];
            int ny = curY + dirY[i];
            
            if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                // 다음으로 방문한 좌표의 색상이 color와 같고 방문한 적 없으면
                if(picture[nx][ny] == color && !visited[nx][ny]) {
                    // 방문 여부 갱신
                    visited[nx][ny] = true;
                    // 방문 좌표 갱신
                    q.push({nx, ny});
                    // 영역 너비 증가
                    size++;
                }
            }
        }
    }
    
    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;
    
    // 방문 배열 초기화
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            visited[i][j] = false;
    
    // 색이 칠해져 있고 방문한적 없으면 bfs 수행
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(picture[i][j] != 0 && !visited[i][j]) {
                // 가장 넓은 영역 구하기
                max_size_of_one_area = max(max_size_of_one_area, bfs(i, j, m, n, picture));
                // 영역 개수 증가
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    
    return answer;
}