백준 16956번 : 늑대와 양 (C 언어)

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

16956번: 늑대와 양

Code:

#include <stdio.h>
 
int r, c;
char arr[500][500] = { 0, };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int flag = 0;
 
void dfs(int y, int x)
{
    for (int i = 0; i < 4; i++)
    {
        int y_n = y + dy[i];
        int x_n = x + dx[i];
       if (arr[y_n][x_n] == 'W')
       {
                flag = 1;
                return;
       }
    }
}
 
int main()
{
    int r, c;
    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] == '.')
            {
                arr[i][j] = 'D';
            }
        }
    }
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (arr[i][j] == 'S')
            {
                dfs(i, j);
                if (flag == 1)
                {
                    break;
                }
            }
        }
        if (flag == 1)
        {
            break;
        }
    }
    if (flag == 0)
    {
        printf("1\n");
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                printf("%c", arr[i][j]);
            }
            printf("\n");
        }
    }
    else if (flag == 1)
    {
        printf("0");
    }
}

문제 설명

크기가 R×C인 목장에서는 각 칸마다 비어있는 칸('.'), 양('S'), 늑대('W')가 있습니다. 양은 그 위치에서 가만히 있고, 늑대는 인접한 칸으로 자유롭게 이동할 수 있습니다. 이때, 목장에 울타리를 설치하여 늑대가 양이 있는 칸으로 갈 수 없게 하려고 합니다. 울타리를 설치하면 해당 칸을 'D'로 표시합니다. 목장을 탈출할 수 있는 경우에는 '1'을 출력하고, 그렇지 않으면 '0'을 출력합니다.

해결 방법

우선 최소 개수의 울타리가 아니므로 모든 '.' 위치에 울타리를 설치했습니다.

1. 목장 탐색 및 울타리 설치
   • 주어진 목장을 탐색하면서 양('S') 주변에 늑대('W')가 있는지 확인합니다. 양의 주변에 늑대가 있으면 울타리를 설치하여 양과 늑대를 분리합니다. 울타리는 해당 칸을 'D'로 표시합니다.
2. 결과 출력
   • 양 주변에 늑대가 없는 상태로 목장을 정리하였으면 '1'을 출력하고, 정리한 목장의 상태를 출력합니다.
   • 양 주변에 늑대가 있어서 목장을 정리할 수 없는 경우에는 '0'을 출력합니다.