BOJ 1926 · 그림

알고리즘 분류 : DFS, BFS  

그림의 개수와 최대 넓이를 구하는 문제다. 플러드 필을 구현하면 된다.

• 아직 확인하지 않은 그림 조각(1)부터 출발하여 인접하여 연결된 모든 그림을 DFS나 BFS로 탐색한다.
• 연결된 그림 조각의 개수는 그림의 넓이를 의미한다. 이중 가장 큰 값이 그림의 최대 넓이이다.
• 그림의 넓이를 확인했으면, 그림의 개수를 카운트한다.

---

C++ 소스코드

#include <cstdio>

int n, m, cnt, area;
int a[500][500];
bool check[500][500];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs(int x, int y) {
    int ret = 1;
    check[x][y] = true;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (!check[nx][ny] && a[nx][ny]) ret += dfs(nx, ny);
    }
    return ret;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (!check[i][j] && a[i][j]) {
                int k = dfs(i, j);
                if (area < k) area = k;
                cnt += 1;
            }
        }
    }
    printf("%d\n%d\n", cnt, area);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
check = [[False]*m for _ in range(n)]
cnt, area = 0, 0

def bfs(i, j):
    q = deque()
    q.append((i, j))
    ret = 1
    check[i][j] = True
    while q:
        x, y = q.popleft()
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not check[nx][ny] and a[nx][ny]:
                q.append((nx, ny))
                check[nx][ny] = True
                ret += 1
    return ret

for i in range(n):
    for j in range(m):
        if not check[i][j] and a[i][j]:
            area = max(area, bfs(i, j))
            cnt += 1
print(cnt)
print(area)

✓ 파이썬은 BFS로 구현했다.

---

참고

• 백준 온라인 저지 : BOJ 1926