백준 3184번 : 양 (C 언어)

Code:

#include <stdio.h>
 
int r, c;
char arr[251][251] = { 0, };
int check[251][251] = { 0, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int sheep = 0;
int wolf = 0;
int s = 0;
int w = 0;
 
void dfs(int y, int x)
{
    check[y][x] = 1;
    if (arr[y][x] == 'o')
    {
        s++;
    }
    else if (arr[y][x] == 'v')
    {
        w++;
    }
    for (int k = 0; k < 4; k++)
    {
        int x_n = x + dx[k];
        int y_n = y + dy[k];
        if (check[y_n][x_n] == 0 && x_n >= 0 && x_n < c && y_n >= 0 && y_n < r && arr[y_n][x_n] != '#')
        {
            dfs(y_n, x_n);
        }
    }
}
 
int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++)
    {
        scanf("%s", arr[i]);
    }
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (arr[i][j] == 'o')
            {
                sheep++;
            }
            if (arr[i][j] == 'v')
            {
                wolf++;
            }
        }
    }
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (arr[i][j] != '#' && check[i][j] == 0)
            {
                s = 0;
                w = 0;
                dfs(i, j);
                if (s > w)
                {
                    wolf -= w;
                }
                else
                {
                    sheep -= s;
                }
            }
        }
    }
    printf("%d %d", sheep, wolf);
}

문제 설명:

이 문제는 미키의 마당에서 일어나는 양과 늑대의 이야기를 모의하는 문제입니다. 마당은 R행과 C열로 이루어진 직사각형 모양으로 표현되며, 각 칸은 '.', '#', 'o', 'v' 중 하나의 문자로 채워져 있습니다.

• '.' (점)는 빈 필드를 나타내며, 마당의 일부를 나타냅니다.
• '#' (울타리)는 마당의 경계를 표시합니다.
• 'o' (양)는 마당에 있는 양을 나타냅니다.
• 'v' (늑대)는 마당에 있는 늑대를 나타냅니다.

양과 늑대는 특별한 규칙에 따라 상호작용하며, 이를 바탕으로 마당에서 살아남은 양과 늑대의 수를 계산해야 합니다. 양은 늑대와 싸울 수 있으며, 어떤 영역 안의 양의 수가 늑대의 수보다 많으면 양이 승리하고, 그 영역의 모든 늑대를 쫓아냅니다. 그렇지 않으면 늑대가 영역 안의 모든 양을 먹습니다.

처음에는 모든 양과 늑대가 마당 안 영역에 존재하며, 아침까지 살아남은 양과 늑대의 수를 출력해야 합니다.

코드 설명:

아래는 주어진 문제를 해결하기 위한 C 코드의 주요 부분입니다.

1. dfs 함수: DFS(Depth-First Search) 알고리즘을 이용하여 영역 내에서 양과 늑대의 수를 계산하는 함수입니다. 현재 위치에서 상하좌우로 이동하며 양과 늑대의 수를 세고, 방문한 위치는 체크합니다.
2.  먼저, 입력으로 주어지는 마당의 크기(R과 C)를 받습니다.
   • 다음으로 R개의 줄에 C개의 글자를 읽어 마당의 상태를 저장합니다.
   • 그리고 전체 양과 늑대의 수를 계산합니다.
   • 이후 모든 칸을 순회하면서 각 영역의 양과 늑대의 수를 계산하고, 승자를 결정하여 전체 양과 늑대 수를 업데이트합니다.
   • 마지막으로, 최종적으로 살아남은 양과 늑대의 수를 출력합니다.