[C++백준 1236번:성 지키기]

문제링크

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

1236번: 성 지키기

 

문제

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

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

입력

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

출력

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

 

해석

행 경비원과 열 경비원을 따로 체크해주고 추가해줘야하는 행, 열 경비원도 따로 세어준다.

추가해줘야 하는 행, 열 경비원의 수 중 큰 것을 출력하도록 한다.

코드

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int n, m;
    string input;
    cin >> n >> m;
 
    string* castle = new string[n];
    bool* r_check = new bool[n];    // 행경비원
    bool* c_check = new bool [m];    // 열경비원
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        castle[i] = input;
    }
    
    for (int i = 0; i < n; i++) {
        r_check[i] = false;
    }
    for (int j = 0; j < m; j++) {
        c_check[j] = false;
    }
 
    // 경비원 있는 위치의 행과 열을 구해 체크
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (castle[i][j] == 'X') {
                r_check[i]= true;
                c_check[j] = true;
            }
        }
    }
 
    int c = 0;    // 열에 추가해야 하는 경비원 수
    int r = 0;    // 행에 추가해야 하는 경비원 수
    for (int i = 0; i < n; i++) {
        if (r_check[i] == false) {    // 없다면 추가
            r++;
        }
    }
    for (int j = 0; j < m; j++) {
 
        if (c_check[j] == false) {    // 없다면 추가
            c++;
        }
    }
    if (c > r) {    // 더 많이 추가해야 하는 경비원 수 출력
        cout << c;
    }
    else {
        cout << r;
    }
}

 

Memo

모든 문제가 그렇지만 이 문제도 풀고 나니 어렵지 않았던 문제였다. 그래도 푸는데까지 꽤나 고전했던 문제이다.

아직 갈길이 멀다. 더 힘내보도록 하자.