greentea31's Note

https://school.programmers.co.kr/learn/courses/30/lessons/1829

풀이 과정

배열로 주어진 그림에서 몇 개의 영역이 있는지, 가장 넓은 영역의 크기는 얼마인지 구하는 문제이다.

그래프에서 연결 요소의 개수와 가장 큰 연결 요소의 크기를 구해달라는 말과 같고, 색칠이 되어 있고, 아직 방문하지 않은 모든 좌표에 대해 BFS 혹은 DFS를 진행해주면 된다.

소스 코드

#include <vector>
#include <queue>
using namespace std;

bool visit[101][101];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int bfs(int y, int x, vector<vector<int>>& picture, int m, int n) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));
    int max_size = 1;
    int color = picture[y][x];
    
    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];
            if (0 <= ny && ny < m && 0 <= nx && nx < n && !visit[ny][nx] && color == picture[ny][nx]) {
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
                max_size++;
            }
        }
    }
    
    return max_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++) {
            if (!visit[i][j] && picture[i][j] != 0) {
                int temp = bfs(i, j, picture, m, n);
                number_of_area++;
                if (max_size_of_one_area < temp) max_size_of_one_area = temp;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            visit[i][j] = false;
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}