1926번: 그림

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

1926번: 그림

배열의 각 성분을 노드, 성분이 상하좌우로 인접한 것을 에지라고 하면 이 문제는 그래프를 순회하며 그래프의 개수와 노드의 수가 가장 많은 그래프를 찾는 문제가 된다. 

- 너비 우선 탐색

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> coord;

#define _y first
#define _x second

#define MAX_N 500

// 그림이 그려진 도화지
bool map[MAX_N][MAX_N];
// N, M: 도화지의 크기, ans: 도화지 안의 그림의 최대 크기
int N, M, ans = 0;

void set_max(int &a, int b) { a = a > b ? a : b; }
// 좌표 + 좌표
coord operator+(coord a, int add[2]) {
    return {a._y + add[0], a._x + add[1]};
}

// 주어진 좌표가 도화지 안의 좌표라면 true, 아니라면 false
bool valid(coord c) {
    return c._y >= 0 && c._y < N && c._x >= 0 && c._x < M;
}

// 주어진 좌표를 포함하는 그림을 탐색
bool bfs(int y, int x) {
    // 한 좌표와 인접한 좌표를 구할 때 사용
    int add[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 그림의 크기
    int size = 0;
    // bfs에 사용할 큐
    queue<coord> q;
    // 가장 먼저 탐색한 좌표를 큐에 넣고 도화지에서 삭제
    q.push({y, x});
    map[y][x] = false;

    while (!q.empty()) {
        // 큐 안의 모든 좌표에 대해
        coord c = q.front();
        q.pop();

        // 좌표 수만큼 size에 1씩 더한다
        size += 1;

        for (int i = 0; i < 4; i++) {
            // 각 좌표와 인접한 좌표에 대해
            coord c_ = c + add[i];
            // 좌표가 도화지 안의 좌표이고 아직 탐색하지 않은 그림이라면
            if (valid(c_) && map[c_._y][c_._x]) {
                // 좌표를 큐에 넣고 그림에서 삭제
                q.push(c_);
                map[c_._y][c_._x] = false;
            }
        }
    }

    // 그림의 최대 사이즈를 갱신
    set_max(ans, size);
    // 연산의 압축을 위해 true를 반환
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int cnt = 0;

    // 문제의 조건을 입력받는다
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++)
        cin >> map[i][j];

    // 각 좌표에 대해 그래프가 존재한다면 bfs를 이용한 탐색
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) 
        if (map[i][j]) cnt += bfs(i, j);

    // 그림의 수와 그림의 최대 크기를 출력
    cout << cnt << '\n' << ans << '\n';

    return 0;
}

 

- 깊이 우선 탐색

#include <cstdio>

bool map[500][500];
int N, M, ans = 0;

void set_max(int& a, int b) { a = a > b ? a : b; }

// 주어진 좌표가 도화지 안의 좌표라면 true, 아니라면 false
bool valid(int y, int x)
{ return y >= 0 && y < N && x >= 0 && x < M && map[y][x]; }

// 그래프를 탐색하며 그래프의 크기를 계산
bool dfs(int y, int x, int& size) {
    // 한 좌표와 인접한 좌표를 구할 때 사용
    int add[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // 현재 위치를 탐색
    map[y][x] = false;
    size += 1;

	// 인접한 위치에 대해 dfs를 실행
    for (int i = 0; i < 4; i++) {
        int y_ = y + add[i][0], x_ = x + add[i][1];
        if (valid(y_, x_)) dfs(y_, x_, size);
    }

	// 그래프의 최대 크기 갱신
    set_max(ans, size);
    // 연산의 압축을 위해 true를 반환
    return true;
}

// 
bool dfs(int y, int x) {
    int temp = 0;
    return dfs(y, x, temp);
}

int main() {
    int cnt = 0;
    
    // 문제의 조건을 입력받는다
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
        scanf("%d", &cnt);
        map[i][j] = cnt != 0;
    }

	// 그래프의 개수를 초기화한 뒤
    cnt = 0;
    // 각 좌표에 대해 그래프가 존재한다면 dfs를 이용한 탐색
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) 
        if (map[i][j]) cnt += dfs(i, j);

    // 그림의 수와 그림의 최대 크기를 출력
    printf("%d\n%d\n", cnt, ans);

    return 0;
}