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

1236번: 성 지키기

문제

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

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

 

입력

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

 

 

출력

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

 

풀이과정

문제의 어떻게 접근을 해야하는가에 대해서 고민을 많이 했었다.

맨 처음 생각했던 방법은 문제에 나와있는 그대로 모든 행과 모든 열에 한 명 이상의 경비원 이라는 조건이 주어져있으니 X가 존재하는
행과 열의 .들을 모두 감시대상이라고 생각을 하고 문제를 풀어보았었다.

#include <iostream>

char arr[51][51];

// 가로 = q, 세로 = w, 둘다 = e
void	change(int n, int m, int y, int x)
{
	for (int k = 0; k < m; k++) {
		if (arr[y][k] != 'X')
			if (arr[y][k] == '.' || arr[y][k] == 'w') {
				if (arr[y][k] == 'w') arr[y][k] = 'e';
				else arr[y][k] = 'q';
			}
	}
	for (int l = 0; l < n; l++) {
		if (arr[l][x] != 'X')
			if (arr[l][x] == '.' || arr[l][x] == 'q') {
				if (arr[l][x] == 'q') arr[l][x] = 'e';
				else arr[l][x] = 'w';
			}
	}
}

int		main(void)
{
	int n, m;
	std::cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			std::cin >> arr[i][j];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 'X') {
				change(n, m, i, j);
			}
		}
	}

	int temp = 0, max = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != 'e' && arr[i][j] != 'X' && arr[i][j] != 'w')
				temp++;
		}
		if (temp > max) max = temp;
		temp = 0;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[j][i] != 'e' && arr[j][i] != 'X' && arr[j][i] != 'q') {
				temp++;
			}
		}
		if (temp > max) max = temp;
		temp = 0;
	}
	std::cout << max;

	return (0);
}

..X.

..X.

..X.

..X.

answer : 3

위와 같은 코드를 조건식으로 만들고 위와 같은 반례를 해결하기위해서 가로를 확인하는 q와 세로를 확인하는 w를 만들어서
2중으로 경비원확인이 되는 e를 제외한 다른 값의 경우 경비원이 필요한 수 라는 식으로 문제를 풀었었다.

 

문제 자체는 해결이 되었었지만 위에 형식의 코드의 경우는 시간복잡도가 너무 복잡하고, 문제도 너무 어렵게 접근을 했던거 같아서

아래와 같은 방법으로 새롭게 접근을 해보았다.

#include <iostream>

char arr[51][51];

int		main(void)
{
	int n, m;
	int yCount = 0, xCount = 0;
	std::cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> arr[i][j];
		}
	}

	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] != '.') break;
			count++;
		}
		if (count == m) xCount++;
		count = 0;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[j][i] != '.') break;
			count++;
		}
		if (count == n) yCount++;
		count = 0;
	}
	if (xCount <= yCount) std::cout << yCount;
	else std::cout << xCount;

	return (0);
}

위와 같은 방식은 X의 기준이 아닌 . 을 기준으로 .의 상하좌우를 확인해서 X가 존재하지않는다면
경비원이 더 필요하다는 식으로 계산을 하여 이전의 코드보다 훨씬 시간복잡도가 덜 걸리게 n^2으로 해결을 했었다.

그렇게 풀이를 마무리하다가 다른분들의 코드와 비교를 했었는데

#include <iostream>

int y[51], x[51];

int		main(void)
{
	int n, m;
	int yCount = 0, xCount = 0;
	char c;
	
	std::cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> c;
			if (c == 'X') {
				if (!y[i]) {
					y[i] = 1;
					yCount++;
				}
				if (!x[j]) {
					x[j] = 1;
					xCount++;
				}
			}
		}
	}
	if (n - yCount <= m - xCount) std::cout << m - xCount;
	else std::cout << n - yCount;

	return (0);
}

위와 같은 형식으로 기존의 코드에서 시간복잡도를 덜어서 훨씬 간단하게 문제를 해결할 수 있다는 것을 발견할 수 있었다.

code

#include <iostream>

int y[51], x[51];

int		main(void)
{
	int n, m;
	int yCount = 0, xCount = 0;
	char c;
	
	std::cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> c;
			if (c == 'X') {
				if (!y[i]) {
					y[i] = 1;
					yCount++;
				}
				if (!x[j]) {
					x[j] = 1;
					xCount++;
				}
			}
		}
	}
	if (n - yCount <= m - xCount) std::cout << m - xCount;
	else std::cout << n - yCount;

	return (0);
}

 

 

후기

발상을 생각해내기가 너무나도 어려운 문제였다.

최대한 시간복잡도를 줄여보고자 고민의 고민을 계속해보고 N^2 까지 줄였으면 많이 줄였다. 라고 생각했었는데

좋은 풀이를 N이면 해결이 되는 문제라는걸보고 감탄과 아쉬움이 많이 남았었다.