백준 14716번 : 현수막 (C 언어)

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

14716번: 현수막

Code:

#include <stdio.h>
 
int m, n;
int arr[251][251] = { 0, };
int check[251][251] = { 0, };
int count = 0;
int dx[] = { -1,1,0,0,1,-1,1,-1 };
int dy[] = { 0,0,-1,1,1,-1,-1,1 };
 
void dfs(int y, int x)
{
    check[y][x] = 1;
    for (int k = 0; k < 8; k++)
    {
        int yn = y + dy[k];
        int xn = x + dx[k];
        if (yn >= 0 && xn >= 0 && yn < m && xn < n && arr[yn][xn] == 1 && check[yn][xn] == 0)
        {
            dfs(yn, xn);
        }
    }
}
 
int main() {
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && check[i][j] == 0)
            {
                count++;
                dfs(i, j);
            }
        }
    }
    printf("%d", count);
}

문제 설명: 주어진 문제는 현수막에서 글자의 개수를 구하는 프로그램을 작성하는 것입니다. 현수막은 0과 1로 이루어진 이차원 배열로 주어지며, 글자 부분은 1로 표시되고, 글자가 아닌 부분은 0으로 표시됩니다. 글자로 판단되는 부분은 상, 하, 좌, 우, 대각선으로 연결되어 있다고 가정합니다. 이를 토대로 글자의 개수를 찾는 것이 목표입니다.

코드 설명: 이 문제를 해결하기 위해 깊이 우선 탐색(DFS)을 사용한 C 프로그램을 작성했습니다. 아래는 코드의 각 부분에 대한 설명입니다.

1. 입력 처리:
   • M과 N은 현수막의 크기를 나타내며, M은 행의 개수, N은 열의 개수입니다. 먼저 이 값을 입력 받습니다.
   • 이어서 M줄에 걸쳐서 현수막의 정보를 입력 받습니다.
2. DFS 함수:
   • DFS 함수는 현수막에서 글자를 찾는 역할을 합니다.
   • (y, x) 좌표를 받아서 해당 좌표가 글자일 경우, 연결된 모든 글자를 찾기 위해 재귀적으로 호출됩니다.
   • DFS를 통해 연결된 모든 글자를 방문 표시하기 위해 check 배열을 사용합니다.
3. 메인 함수:
   • 입력 처리 후, 현수막을 순회하며 각 글자를 찾습니다.
   • 만약 arr[i][j]가 1이고, 아직 방문하지 않은 글자인 경우, DFS 함수를 호출하여 현재 글자와 연결된 모든 글자를 탐색합니다.
   • 탐색이 끝날 때마다 글자의 개수(count)를 1 증가시킵니다.
   • 모든 현수막을 순회한 후, 글자의 총 개수(count)를 출력합니다.