[백준 - C#] 1236번 성 지키기

문제링크

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

1236번: 성 지키기

 

문제

영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다.
영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다.
N과 M은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 성의 상태가 주어진다.
성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.

출력

첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.

 

문제정리

1. 모든 행과 모든 열에 한 명 이상의 경비원이 있어야 합니다.
2. N,M <= 50
3. 몇 명의 경비원을 최소로 추가 해야하는지 구해야합니다.

이번 문제의 경우 경비원을 구하는 문제입니다. 문제의 요지는 모든 행과 모든 열에 한 명 이상의 경비원만 있으면 되기 때문에 각 열이나 행에 대해서 순차적으로 경비원이 있는지 없는지 체크하며 있으면 다음 열이나 행으로 없으면 경비원을 카운팅 하는 방식으로 문제풀이를 접근 하였습니다.

처음에는 if 문으로 N행과 N열을 비교하여 큰 수로만 처리를 하였으나, 생각해보니 N행과 M열을 따로 계산하여 더 많이 필요로 하는 경비원의 값이 정답이였습니다.

 

예제 입력 3를 가지고 설명하자면

5 8
....XXXX
........
XX.X.XX.
........
........

N을 기준으로 계산을 하면 필요로 하는 경비원의 수는 1입니다.

M을 기준으로 계산을 하면 필요로 하는 경비원의 수는 3입니다.

하지만 정답의 경우 필요로 하는 최소 경비원의 수는 3으로써 N과 M의 필요로하는 경비원의 수 중 큰수를 찾으면 됩니다.

 

아래의 코드를 보면 더 쉽게 파악하실 수 있으실 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);
 
    string[] array = new string[N];
 
    for (int i = 0; i < N; i++)
        array[i] = reader.ReadLine();
 
    int columCount = 0;
 
    // 행에서 경비원이 필요한 숫자 계산
    for (int i = 0; i < N; i++)
    {
        bool isGuard = false;
        for (int j = 0; j < M; j++)
        {
            if (array[i][j] == 'X') // N행에서 경비원이 한명이라도 있으면 패스
            {
                isGuard = true;
                break;
            }
        }
 
        if (!isGuard) // N행에 경비원이 한명도 없으면 추가
            columCount++;
    }
 
    int rowCount = 0;
 
    // 열에서 경비원이 필요한 숫자 계산
    for (int i = 0; i < M; i++)
    {
        bool isGuard = false;
        for (int j = 0; j < N; j++)
        {
            if (array[j][i] == 'X') // M열에서 경비원이 한명이라도 있으면 패스
            {
                isGuard = true;
                break;
            }
        }
 
        if (!isGuard) // M열에 경비원이 한명도 없으면 추가
            rowCount++;
    }
 
    // 경비원이 더 큰수를 출력
    writer.WriteLine((rowCount > columCount) ? rowCount : columCount);
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.