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

🌱 문제 설명

1236번 성 지키기

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

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

---

입력

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

---

출력

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

풀이

#include<iostream>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    int check_row = 0;
    int check_col = 0;
    
    char arr[N][M]; // 문자열 배열
    bool row[50] = {false}; // 행
    bool col[50] = {false}; // 열
    
    // 배열 입력받고 경비원이 있는지 검사
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> arr[i][j]; // 배열 입력 받기
            if(arr[i][j] == 'X') { // 'X'이면 경비원이 있으니까
                row[i] = true;
                col[j] = true;
            }
        }
    }

    // 경비원이 없는 행의 수 검사
    for(int i = 0; i < N; i++) {
        if(!row[i]) {
            check_row++;
        }
    }

    // 경비원이 없는 열의 수 검사
    for(int j = 0; j < M; j++) {
        if(!col[j]) {
            check_col++;
        }
    }

    // 행과 열 중 더 없는 쪽의 갯수에 맞게 경비원을 세운다.
    int answer = max(check_row, check_col);
    cout << answer << endl;

    return 0;
}

❣️문제 요약:

입력받은 크기의 문자 배열을 입력 받아서 모든 행과 열에 X(경비원) 가 하나 이상 들어가도록 추가해야하는 X의 최솟값을 구한다.

🤔 생각해야 할 점

1. 모든 행과 열에 경비원이 최소 하나 있도록 해야한다.

2. 현재 어느 열과 행에 경비원이 존재하는지 파악한다.

3. 모든 행에서 몇개의 행에 경비원이 없는지 파악하고 몇개의 열에 경비원이 없는지 파악해서

   더 적은 수의 경비원을 가진 쪽 만큼 경비원을 추가하면 최소로 경비원을 추가하면서 모든 행과 열에 경비원을 배치할 수 있다.

→ 행, 열의 경비원 수를 검사해서 더 없는 쪽에 맞게 경비원 수를 추가한다.

코드 설명

✅ 입력받을 문자열 배열과 행과 열을 검사할 bool 배열 생성

    char arr[N][M]; // 문자열 배열
    bool row[50] = {false}; // 행
    bool col[50] = {false}; // 열

✅ 이중 for문으로 배열을 입력받고 각 인덱스에 X가 있는지 검사하고 행 열 배열에 true

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> arr[i][j]; // 배열 입력 받기
            if(arr[i][j] == 'X') { // 'X'이면 경비원이 있으니까
                row[i] = true;//행에 경비원이 있음을 표시
                col[j] = true;//열에 경비원이 있음을 표시
            }
        }
    }

✅경비원이 없는 행의 수가 몇개인지 세서 check_row 에 저장

    // 경비원이 없는 행의 수 검사
    for(int i = 0; i < N; i++) {
        if(!row[i]) {
            check_row++;
        }
    }

✅ 행과 열 중 더 적은 수의 경비원을 가진 쪽을 max로 찾아서 반환

  int answer = max(check_row, check_col);
  cout << answer << endl;