Codeforces Round #744 (Div. 3)-C. Ticks

문제 설명

지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다.

$i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자.

지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다.

1. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다.
2. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한다.
3. 모든 격자를 칠하면 $0$과 $d$사이에 있는 모든 $h$에 대해서 $(i - h, j + h)$ 인 좌표를 가진 격자는 모두 검은색으로 색칠 되어있다. 즉 V모양은 $2d + 1$개의 검은 격자로 이루어져 있다.

우리는 지니한테 $n \times m$ 모양의 격자판을 받았다. 지니는 이 격자판이 최소 크기가 $k$인 V모양으로 구성될 수 있는지 아닌지를 확인하고 싶다. 즉 모든 V모양의 크기는 k보다 크거나 같아야 한다. $(d \ge k)$

Input
첫번째 줄은 테스트케이스의 수 $t (1 \le t \le 100)$가 주어진다.

각 테스트 케이스의 첫번째 줄에는 판의 크기와 지니가 그릴 수 있는 V모양의 최소 크기를 나타내는 정수 $n, m, k (1 \le k \le n \le 10, 1 \le m \le 19)$가 주어진다.

뒤따르는 $n$개의 줄에는 판의 형태를 나타낸다. 각 줄은 $m$개의 문자로 이루어져 있고 만약 격자가 흰색으로 색칠되었다면 '.', 검은색으로 색칠되었다면 '*'이다.

Output
각 테스트 케이스마다 답을 출력한다.
만약 주어진 판이 주어진 크기를 최소 크기로 가지는 V모양으로 색칠 할 수 있으면 "YES"를, 아니면 "NO"를 출력한다. 이때 출력하는 문자열은 어떤 형태이든 상관이 없다.

Example
input
8
2 3 1
* . *
. . .
4 9 2
* . * . * . . .*
. * . * . . . * .
. . * . * . * . .
. . . . . * . . .
4 4 1
* . * .
* * * *
. * * .
. . . .
5 5 1
. . . . .
* . . . *
. * . * .
. . * . *
. . . * .
5 5 2
. . . . .
* . . . *
. * . * .
. . * . *
. . . * .
4 7 1
* . . . . . *
. . . . . * .
. . * . * . .
. . . * . . .
3 3 1
* * *
* * *
* * *
3 5 1
* . . . *
. * * * .
. * * . .

output
NO
YES
YES
YES
NO
NO
NO
NO

문제 접근

사용한 알고리즘: 그리디, 구현
걸린 시간 : 00:19
virtual test 진행중일 때 문제를 딱 보자마자 이건 못풀겠다하고 바로 다음 문제로 넘어간 문제이다. 딱 이정도 문제를 풀 수 있으면 블루까지 도전해 볼만하다는 생각을 이 문제의 해설을 보면서 느꼈다.

먼저 아래에서부터 위로 올라가는 대각선을 두개 그리기 때문에 반복문을 위에서 아래부터 하는 것이 아닌 아래에서 위로 했으면 좋을 것 같다는 생각을 먼저 했으면 좋았을 것 같았다.

그리고 반드시 대각선 상에 있는 모든 격자를 색칠해야 하기 때문에 색칠이 도중에 비어있어도 V모양을 그릴 수 없다.

이 두가지 사실을 가지고 문제를 차근차근 풀어보자.
아래에서 위로 반복문을 시작한다. 이때 검은색으로 색칠된 부분에서 이 부분을 중앙으로 하고, 크기가 k이상인 V모양을 그릴 수 있는지 판별하는 반복문을 실행한다. 이때 이미 중앙은 색칠이 되어있기 때문에 중앙보다 한단계 위에 있는 격자부터 색칠을 할 수 있는지 확인 해야한다. 중앙에 있는 격자가 딱 0번째 열이거나, 딱 m - 1번째 열이거나 맨 위에 있는 행이면 다음 격자를 색칠 할 수 없기 때문에 while문에 있는 조건문의 형태가 조금 이상한 것이다.
거기에 도중에 끊어진 부분이 있는지도 확인해야 하기 때문에 while문 안에 있는 조건문으로 확인했다.

이 반복문을 통해서 계속 색칠 할 수 있는 크기인 len을 늘려나갔기 때문에 반복분이 종료되면 V모양의 크기가 구해진다. 테스트 케이스에서 주어진 값인 k를 바탕으로 색칠했다는 표시를 한다.

모든 과정이 끝나고 나서 아직 색칠 안되어있다는 표시가 존재하면 이 판은 최소 크기가 k인 V모양으로 색칠 할수 없기 때문에 "NO"를 출력하고 아니면 "YES"를 출력한다. 이때 $d = 0$인 경우는 생각안해도 된다. 왜냐하면 입력 케이스의 조건에서 k는 항상 1보다 크기 때문에 중앙 부분만 색칠 되어있는 크기가 0인 V모양은 항상 색칠이 안되어있다고 표시가 될 것이기 때문이다.

정답 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, m, k; cin >> n >> m >> k;
        int status[n][m];
        for(int i = 0; i < n; i++){
            string str; cin >> str;
            for(int j = 0; j < m; j++) status[i][j] = (str[j] == '*');
        }

        for(int i = n - 1; i >= 0; i--){
            for(int j = 0; j < m; j++){
                if(!status[i][j]) continue;

                int len = 0;
                while(j - len > 0 && j + len + 1 < m && i - len > 0){
                    if(!status[i - len - 1][j - len - 1] || !status[i - len - 1][j + len + 1]) break;
                    len++;
                }

                if(len < k) continue;
                for(int d = 0; d <= len; d++){
                    status[i - d][j - d] = 2;
                    status[i - d][j + d] = 2;
                }
            }
        }

        bool flag = false;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(status[i][j] == 1){
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        cout << (flag ? "NO" : "YES") << "\n";
    }
    return 0;
}