백준 29634번 : Hotel (C 언어)

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

29634번: Hotel

Code:

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

문제 설명:

Pavel은 어릴 적부터 건축가가 되기를 꿈꿔왔습니다. 종종 건물 계획을 종이, 때로는 탁자나 벽에 그리곤 했습니다. 이제 그는 대학 학위를 취득하고 유명한 건축가가 되었습니다.

어느 날 Pavel은 어릴 적 그림 중에서 호텔 층 구조에 대한 흥미로운 계획을 발견했습니다. 이 바닥은 $n \times m$ 미터 크기의 직사각형이며, 각 정사각미터는 파란색 또는 빨간색으로 칠해져 있습니다. 고민 끝에 Pavel은 파란색이 복도를 나타내고 빨간색이 호텔 객실을 나타내는 것을 이해했습니다.

어린 시절부터 Pavel은 국제 표준을 준수하려 노력했습니다. 국제 표준에 따르면 호텔 객실은 직사각형이어야 하며 바닥 계획상에서 빨간색으로 표시되어야 합니다. 객실의 변은 바닥 경계에 평행해야 합니다. 또한 각 호텔 객실 주변에는 항상 복도가 있어야 합니다.

소방 안전 규정을 준수하기 위해 바닥의 가장자리에는 반드시 복도가 있어야 합니다. 따라서 바닥 계획의 첫 번째 및 마지막 행, 그리고 첫 번째 및 마지막 열은 파란색입니다.

Pavel은 자신의 계획을 살펴보며 그 계획에서 호텔 객실의 최대 면적은 얼마인지 궁금해합니다. 이 문제에서는 이 최대 면적을 찾는 프로그램을 작성해야 합니다.

 

코드 설명:

1. 입력을 받아와서 바닥 계획을 배열 arr에 저장합니다.
2. DFS 함수를 사용하여 빨간색 정사각미터(호텔 객실)의 영역을 찾고 해당 영역의 크기를 계산합니다.
3. 모든 빨간색 영역에 대한 크기를 계산하면서 최대 크기를 갱신합니다.
4. 만약 빨간색 영역(호텔 객실)이 하나도 발견되지 않는 경우 -1을 출력하고, 그렇지 않으면 가장 큰 호텔 객실의 면적을 출력합니다.