SWEA4014.md

활주로 건설

https://swexpertacademy.com/ [4014]

개요

N*N(<=20)의 지도가 주어지고 높이가 1이고 길이가 X(2<=X<=4)인 경사로가 주어진다. 행과 열 단위로 활주로를 건설할 수 있는지 총 건설가능한 행과 열의 개수를 출력하면 된다.

분석

한 행을 검사하는 함수를 만들고 2*N개의 행과 열을 넣어주는 것이 가장 간단한 구현인 것 같다. 값이 1증가, 감소하는 지점이외의 경우는 모두 활주로를 건설할 수 없기 때문에 바로 검사를 중단하는 것도 연산을 줄일 수 있는 방법이라고 생각한다.

알고리즘

1. 행과 열을 1차원 배열에 복사한다.

2. 1차원 배열을 탐색하며 값이 변하는 지점을 찾는다.

3. 값이 1 감소하는 지점이라면 변하는 지점(i)부터 i+X-1까지 값이 변하지 않고 기존경사로가 건설되지 않았는지를 검사한다.

4. 값이 1 증가하는 지점이라면 변하는 지점에서 X만큼 떨어진 지점(i-X)부터 i-1까지 값이 변하지 않고 기존 경사로가 건설되지 않았는지를 검사한다.

5. 만약 조건에 맞지 않는다면 검사를 중단하고 다음 행이나 열로 넘어간다.

6. 2~5반복

소스

#include <stdio.h>
 
int chkp(int n, int x, int *d)
{
    int su, i, j, *chk, flag;
    chk = (int*)malloc(sizeof(int)*n);
    for (i = 0; i < n; i++) chk[i] = 0;
    su = d[0];
    for (i = 1; i < n; i++)
    {
        if (su > d[i])
        {
            if (d[i] + 1 != su) return 0;
            if (i + x <= n)
            {
                for (j = i; j < i + x; j++)
                {
                    if (d[i] != d[j] || chk[j] == 1) return 0;
                    chk[j] = 1;
                }
            }
            else return 0;
        }
        else if (su < d[i])
        {
            if (d[i] != su+1) return 0;
            if (i - x >= 0)
            {
                for (j = i - x; j < i; j++)
                {
                    if (su != d[j] || chk[j] == 1) return 0;
                    chk[j] = 1;
                }
            }
            else return 0;
        }
        su = d[i];
    }
    return 1;
}
 
int process(int n, int x, int **map)
{
    int i, j, h, *d, sum = 0;
    d = (int*)malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
    {
        d = map[i];
        if (chkp(n, x, d) == 1) ++sum;
    }
    d = 0;
    free(d);
    d = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            d[j] = map[j][i];
        }
        if (chkp(n, x, d) == 1) ++sum;
    }
    free(d);
    return sum;
}
 
int main()
{
    int T, N, X, **map, i, j, k, *answer;
    scanf("%d", &T);
    answer = (int*)malloc(sizeof(int)*T);
    for (i = 0; i < T; i++)
    {
        scanf("%d%d", &N, &X);
        map = (int**)malloc(sizeof(int*)*N);
        for (j = 0; j < N; j++)
        {
            map[j] = (int*)malloc(sizeof(int)*N);
            for (k = 0; k < N; k++)
            {
                scanf("%d", &map[j][k]);
            }
        }
        answer[i] = process(N, X, map);
        for (j = 0; j < N; j++) free(map[j]);
        free(map);
    }
    for (i = 0; i < T; i++) printf("#%d %d\n", i + 1, answer[i]);
 
}