[백준/C++] 1236 성 지키기

문제

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

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

입력

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

출력

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

#include <iostream>
#include <stdbool.h>
using namespace std;

int main()
{
	int n, m, row, col, rowcount = 0, colcount = 0;
	bool flag;
	char arr[50][50] = {};
	cin >> n >> m;
	row = n, col = m;
	
	for (int i = 0; i < n; i++) {
		flag = true;
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'X') {
				flag = false;
				//break;			입력을 받아야되니까
			}
		}
		if (flag == false) row--;
	}
	for (int j = 0; j < m; j++) {
		flag = true;
		for (int i = 0; i < n; i++) {
			if (arr[i][j] == 'X') {
				flag = false;
				break;
			}
		}
		if (flag == false) col--;
	}
	cout << max(row, col) << endl;
}

해결: 모든 행과 열이 경비원이 필요하다고 가정하고 만약 이미 경비원이 있다면 하나씩 줄이는 방식

2차원 배열을 사용

각 행과 열을 검사하여 만약 어떤 행이나 열에 X가 있다면(즉, 이미 경비원이 있다면) flag를 false로 바꿈

해당 행이나 열의 flag가 false라면(이미 경비원이 있다면), 그 행이나 열은 경비원이 필요없는 것이므로 앞에서 미리 경비원이 필요하다고 가정했던 것을 감소시켜줌

행에서 필요한 경비원, 열에서 필요한 경비원 중 최댓값을 출력