백준 11123번 : 양 한마리... 양 두마리...(C 언어)

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

11123번: 양 한마리... 양 두마리...

Code:

#include <stdio.h>
 
int h, w;
char arr[101][101] = { 0, };
int check[101][101] = { 0, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void dfs(int y, int x)
{
    check[y][x] = 1;
    for (int k = 0; k < 4; k++)
    {
        int y_n = y + dy[k];
        int x_n = x + dx[k];
        if (y_n >= 0 && y_n < h && x_n >= 0 && x_n < w && check[y_n][x_n] == 0 && arr[y_n][x_n] == '#')
        {
            dfs(y_n,x_n);
        }
    }
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &h, &w);
        int count = 0;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                check[i][j] = 0;
                arr[i][j] = 0;
            }
        }
        for (int i = 0; i < h; i++)
        {
            scanf("%s", arr[i]);
        }
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (check[i][j] == 0 && arr[i][j] == '#')
                {
                    count++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", count);
    }
}

문제 설명

어느 날, 불면증으로 시달리던 당신은 친구 광민이의 조언에 따라 양을 세는 것을 시작했습니다. 어느 날 밤, 양을 세다가 이것을 프로그래밍 문제로 바꿀 수 있겠다는 아이디어가 떠올랐습니다. 이 문제에서는 주어진 그리드에서 양의 무리를 찾아내는 프로그램을 작성해야 합니다.

각 그리드는 '#'로 나타내며, 무리를 이루는 양은 서로 인접한 '#'들의 집합으로 정의됩니다. 여러 테스트 케이스가 주어질 것이며, 각 테스트 케이스에서 얼마나 많은 양 무리가 있는지를 출력해야 합니다.

코드 설명

 

1. dfs 함수: DFS를 사용하여 양 무리를 찾는 함수입니다. 주어진 좌표 (y, x)를 시작으로 주변의 양을 찾아냅니다. 이미 방문한 좌표는 check 배열을 사용하여 표시합니다.
2. main 함수: 프로그램의 주 진입점입니다. 테스트 케이스 수를 입력받고, 각 테스트 케이스마다 그리드의 크기와 모양을 입력받습니다. 그 후, 모든 좌표를 검사하여 양 무리의 수를 계산하고 출력합니다.
3. check 배열: 이미 방문한 좌표를 표시하기 위한 배열로, 초기에 모든 값을 0으로 초기화합니다.
4. dx와 dy 배열: 상하좌우 이동을 나타내는 배열로, dfs 함수에서 사용됩니다.