BOJ 14716 · 현수막

알고리즘 분류 : DFS  

현수막에 쓰여있는 문자의 개수를 출력하는 문제다. 전형적인 플러드 필 문제이며, 인접한 8방향을 처리하면 된다.

• M*N 사이즈의 맵을 DFS로 탐색하면서 연결된 글자(1)를 따라 이동하면 된다.
• 인접한 8방향(상, 하, 좌, 우, 대각선)으로 이동한다.
• 글자의 개수를 카운트한다.

---

C++ 소스코드

#include <cstdio>

int m, n, ans;
int a[250][250];
bool check[250][250];
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

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

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

---

Python 3 소스코드

import sys
sys.setrecursionlimit(100000)

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

def dfs(x, y):
    check[x][y] = True
    for dx, dy in (-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,-1), (1,1):
        nx, ny = x+dx, y+dy
        if nx < 0 or nx >= m or ny < 0 or ny >= n:
            continue
        if not check[nx][ny] and a[nx][ny]:
            dfs(nx, ny)

for i in range(m):
    for j in range(n):
        if not check[i][j] and a[i][j]:
            dfs(i, j)
            ans += 1
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 14716