[백준/C++] 1926번 : 그림

 

풀이

• DFS를 활용하여 그림의 영역을 찾는다. 각각의 1로 이루어진 영역은 하나의 그림을 의미함. 따라서 DFS를 사용하여 연결된 1의 영역을 찾아내고, 각 그림의 넓이를 계산한다.
• FS 함수는 현재 위치 (x, y)에서 상하좌우로 탐색하며 연결된 영역을 찾아간다. 이때 주의해야 할 점은, 대각선으로는 연결되어 있지 않다고 하였으므로 상하좌우만 고려해야 한다.
• 만약 (x, y) 위치가 유효하고 아직 방문하지 않았으며, 값이 1이라면, 해당 위치를 방문한 것으로 표시하고 그림의 넓이를 1 증가시킨다. 그리고 이어서 인접한 위치들도 DFS를 호출하여 같은 그림에 속하는지 확인한다.
• 모든 위치를 순회하면서 그림의 개수와 가장 큰 그림의 넓이를 찾는다.
• 가장 큰 그림의 넓이를 출력한다.

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> paper;
vector<vector<bool>> visited;

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

int dfs(int x, int y) {
    visited[x][y] = true;
    int area = 1;

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && paper[nx][ny] == 1) {
            area += dfs(nx, ny);
        }
    }

    return area;
}

int main() {
    cin >> n >> m;
    paper.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> paper[i][j];
        }
    }

    int num_of_paintings = 0;
    int max_area = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (paper[i][j] == 1 && !visited[i][j]) {
                num_of_paintings++;
                int area = dfs(i, j);
                max_area = max(max_area, area);
            }
        }
    }

    cout << num_of_paintings << endl;
    cout << max_area << endl;

    return 0;
}

 

 

https://www.acmicpc.net/problem/1926

1926번: 그림