[BOJ - 1926] 그림 (C++)

  문제

 

  접근방법

[BOJ - 6186] Best Grass(C++)

내가 풀었던 문제와 유사하다, 그러나 그림의 최대 크기를 계산해야 하는 부분이 추가

explore(dfs 실행) 함수 내에서 int area 변수를 통해 조건을 만족할 때마다 area 변수를 갱신

-> 반복문을 main 함수 안에서 직접 돌려 largestArea를 갱신

 

  코드

#include <iostream>

using namespace std;

const int MAX = 501;

int n, m;
int canvas[MAX][MAX];
bool visited[MAX][MAX];

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

bool inArea(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// DFS
int explore(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 (inArea(nx, ny) && !visited[nx][ny] && canvas[nx][ny] == 1) {
            area += explore(nx, ny);
        }
    }

    return area;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // 초기값 세팅
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> canvas[i][j];
        }
    }

    int largestArea = 0;
    int pictureCount = 0;

    // 모든 칸 탐색
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (canvas[i][j] == 1 && !visited[i][j]) {
                largestArea = max(largestArea, explore(i, j));
                pictureCount++;
            }
        }
    }

    cout << pictureCount << '\n' << largestArea;

    return 0;
}

 

 

가독성 향상 시킨 뒤 코드 -> 이쁘다...

 

  링크

1926번: 그림