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

www.acmicpc.net/problem/1236

1236번: 성 지키기

 

1. 서론

 

좀 자신감을 가지고 풀어야 하는 문제... 긴가민가 싶은데 그게 맞다. (근데 문제를 다 푼 이 순간에도 이게 맞나 싶음)

 

2. 문제 풀이

 

문자형 배열이 주어진다. '.'는 비어있는 거고 'X'는 경비원이 있는 것이다. 모든 행과 열에는 경비원이 있어야 한다. 그러기 위해 몇 명의 경비원을 최소로 배치해야 하는지를 구하는 문제다. 

 

처음에는 어떻게 해야 '최소'로 인원을 추가할 수 있을까 이게 너무 어렵게 느껴졌다. 그래서 몇 가지 테스트 케이스를 만들어서 방법을 생각해냈다. 

 

 

 

 

 

 

예를 들어

 

. . X .

. X . .

. . . .

 

이런 입력이 주어진다. 배열을 기준으로 2번째 가로행과 0,3번째 세로행에 경비원이 없다. 

그럼 이 상태에서 어떻게 최소로 경비원을 배치할 수 있을까?

내가 생각한 방법은 이렇다.

2번째 가로행과 0,3번째 가로행 어디든 경비원을 배치해도 상관없는 상황이다.

그래서 최소로 배치를 하기 위해 2,0이나 2,3 중에 한 곳에 경호원을 배치한다. 그리고 만약 2,0에 배치를 했다고 가정하면 3번째 가로행 어떤 곳이든 경비원을 배치해도 상관없으므로 최소로 배치하는 경호원은 2명이 된다.

즉, 최소로 배치를 하기 위해서는 가로, 세로를 하나의 좌표로 만들어 경비원을 배치해야 한다. 그리고 남은 곳에는 무조건 다른 경비원을 배치해야 하므로 가로와 세로행 중 더 경비원을 많이 필요로 하는 곳의 수가 최소로 배치해야 하는 경비원의 인원 수가 되는 것이다. 

 

그래서 난 가로를 기준으로 배열을 검사해서 경비원이 부족한 행을 검사하고, 세로도 마찬가지로 검사한 후에 그 수가 더 큰 것을 답으로 출력했다.

 

 

 

 

 

 

3. 코드 설명

 

#include <iostream>

using namespace std;

int main()
{
    int i, j, n, m, f = 0, r = 0, c = 0, result;
    char a[50][50];

    cin >> n >> m;

    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            cin >> a[i][j];
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
            if (a[i][j] == 'X')
                f = 1;
        if (f == 0) r++;
        f = 0;
    }

    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
            if (a[j][i] == 'X')
                f = 1;
        if (f == 0) c++;
        f = 0;
    }
    
    result = (r > c) ? r : c;

    cout << result << endl;
}

 

 

배열을 입력받은 후 가로를 기준으로 X가 있는지 없는지 검사한다.

X가 있으면 그냥 넘기고 없으면 r에 count 해준다.

세로도 이와 마찬가지로 반복한 후 c에 count 해준다.

그리고 r과 c를 크기 비교 후 크기가 큰 것을 답으로 출력해준다.

 

아직도 뭔가 긴가민가하고 틀린 테스트 케이스가 어딘가 있을 것 같은데... 맞다니까 됐다!