백준 1236번 성 지키기

https://www.acmicpc.net/

Baekjoon Online Judge

2차원 행렬을 이용하는 문제이다.

입력이 2차원 행렬이고 문자다.

[문제 해석]

직관적으로 문제를 딱 보고 떠올린 점은, 가로 세로 행렬을 반복문으로 돌려서 'X' 가 없는 부분을 공략하자! 였다.

첫번째 줄 입력은 2차원 행렬을 입력하게 될 가로, 세로의 길이가 각각 N , M으로 주어진다.

두번째 줄에서부터는 2중 반복문을 활용해 'X' 가 빈 곳을 찾아나가면 된다.

나의 경우 코드의 전체 흐름은, 2중 반복문을 두번 사용하는 것이다.

1. 가로줄의 'X' 가 빈 곳을 찾기위해

2. 세로줄의 'X' 가 빈 곳을 찾기위해

 

[코드 해석]

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

// 헤더는 어떤걸 사용할지 모르니 다양하게~

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    // 입출력에 있어 시간을 줄여준다!

	int a, b;
	cin >> a >> b;
	vector<vector<char>> ab(a,vector<char>(b,','));
	char ab_sub;
    
    // N x M 행렬을 만들기 위해 a,b 변수를 각각 할당하여 입력해주었다.
    // '.' 과 'X' 로 이루어진 행렬을 담기위해 간편한 벡터 ab를 선언해주었다.
    // 벡터 해석 : 입력해준 a크기의 공간을 만들고, 공간안에 b크기의 공간을 다시 만들어 ','로 채움
    // 			 즉, a x b 크기에 ',' 로 채워둔 것이다. (ab_sub는 ab를 입력받기위한 임시 변수)
    

	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			cin >> ab_sub;
			ab[i][j] = ab_sub;
		}
	}
    
    // a x b 크기만큼 ab 2차원 벡터에 문자열 값을 입력에 맞게 바꿔준다.
    // '.' 이랑 'X' 로 이루어진다.
    
	int count = 0;
	int res = 0;
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			if (ab[i][j] == 'X')
			{
				count = 1;
			}
		}
		if (count == 0)
		{
			res++;

		}
		count = 0;
	}
    
    // 2중 반복문을 통해 가로줄을 먼저 탐색하자!
    // 가로줄에서 'X'가 발견되면 count라는 변수를 만들어 1이라고 바꾼다.
    // 즉, 'X'를 발견하지 못하면 count=0이 되고, 
    //		'X'를 추가한다는 의미에서 결과값의 수를 담을 res 변수에 1을 더해준다.
    // 한줄 한줄마다 count = 0 으로 초기화 조심!
    
	int q;
	q = res;
	res = 0;
    
	// !!!여기가 중요한 부분인데!!!
    // 변수 q를 만들어 res값을 할당한다. (가로, 세로 탐색할때 중복을 방지하기 위해 필요하다!)
    // res 값은 세로를 탐색하기 위해 다시 0으로 초기화해준다.
    
	for (int i = 0; i < b; i++)
	{
		for (int j = 0; j < a; j++)
		{
			if (ab[j][i] == 'X')
			{
				count = 1;
			}
		}
		if (count == 0)
		{
			res++;
		}
		count = 0;
	}
    
    // 이번에는 2중 반복문을 이용해 세로를 탐색하자!
    // 마찬가지로 'X'가 발견되면 1, 아니면 0
    // res에 'X'가 발견되지 않은 세로줄만큼 값이 저장되어있을거다.
    
	if (res <= q)
	{
		cout << q;
	}
	else
	{
		cout << res;
	}
    
    // 이제 결과를 확인할 시간이다...
    // 좀 전에 만들어주었던 q변수의 값과 다시 초기화해주어 세로를 탐색하고 얻은 res 변수값을 비교해준다.
    // 가로줄에서 'X'가 비어있던 곳만큼 채워줬다고 가정한다면, 
    //		세로줄에서 'X'가 비어있는 곳은 가로줄에서 채워준 'X'의 위치를 바꿔서 대체해줄 수 있다.
    //		즉, 가로줄에서 'X'를 채워줬는데 세로줄에서 또 채워줄 필요 없으므로 중복을 방지하기위해,
    //			가로줄에서 발견한 빈부분의 숫자(q)가 세로줄에서 발견한 빈부분의 숫자(res)보다 크거나 같다면,
    //			세로줄을 가로줄이 전부 대체할 수 있고, 가로줄만 추가해주면 되며, q를 출력해준다.
    //			반대는 세로줄 채워줄게 더 많다는 얘기이므로 가로줄을 탐색하고 res = 0으로 초기화해주었으니, res를 출력한다.
    
    //!!!!!!!!!!!!!!!핵심은 가로의 빈곳을 채워줄 때, 세로의 빈곳을 채워주면서 중복이 발생할 수 있다는 것!!!!!!!!!!!!!!!!!!!!!!
}

코드에 주석을 전부 달아두었으니 참고해주길 바란다.

이 문제의 핵심 요약은,,, 가로 세로의 빈곳을 'X' 로 채워주는데 있어 중복 발생을 염두