[SWEA] 4014. 활주로 건설

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH 

SW Expert Academy

 

문제 이해

배열을 얼마나 자유자재로 다루는지를 보는 문제인 것 같다. 

그리고 문제에 나와있지 않은 예외 사항을 잘 캐치하는지를 보는 것 같다. 

 

사실 아이디어는 단순하다. 

배열을 가로/세로로 한 줄 탐색하면서 만약에 높이가 달라지면 낮은 쪽에 연속으로 경사로 길이 X 만큼의 공간이 있는지를 확인하면 된다. 

 

나는 check()라는 함수를 만들어서 위의 조건을 확인했다. 

그러기 위해서 세로와 가로 줄을 tmp라는 전역 배열에 복사해주고, check는 tmp를 가지고 계산하도록 했다. 

for문으로 배열을 순차 탐색(tmp[x-1]과 tmp[x]를 비교, x는 1부터 N-1까지)하면서 (a)낮아지는 경우 와 (b)높아지는 경우 로 나눈다.

 

(a) 낮아지는 경우

 이 경우에는 뒤쪽(tmp[x])부터 X번 뒤로 해당 높이가 있는지를 확인한다. 

    - X번을 못 채운 채로 배열 범위를 넘어가면 (i>=N) 당연히 --> 불가능

    - X번 내에 tmp[x]와 값이 다른 애가 존재 (높이가 달라짐) --> 불가능

    - 높이 차가 1이상인 경우 --> 공간이 있어도 경사로를 못지음 --> 불가능 

 

(b) 높아지는 경우

 이 경우에는 앞쪽(tmp[x-1])부터 X번 앞으로 해당 높이가 있는지를 확인한다. 

    - X번을 못 채운 채로 배열 범위를 넘어가면 (i < 0) 당연히 --> 불가능

    - X번 내에 tmp[x]와 값이 다른 애가 존재 (높이가 달라짐) --> 불가능

    - 높이 차가 1이상인 경우 --> 공간이 있어도 경사로를 못지음 --> 불가능 

 

난 마지막 조건인 높이 차가 1이상인 경우에는 경사로를 못짓는다 는 조건을 간과해서 헤맸다.

 

작성 코드 (C)

#include <stdio.h>

int T;
int N; // 지도 한 변의 길이
int X; // 경사로의 길이
int map[20+5][20+5];    // 지도
int tmp[20+5];

void getInput(void){
    scanf("%d %d", &N, &X);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            scanf("%d", &map[i][j]);
        }
    }
}

int check(void){
    int used[20+5] = {0,};
    for(int x = 1; x<N; x++)
    {
        if(tmp[x-1] == tmp[x]) continue; // 문제없음
        else if(tmp[x] - tmp[x-1] == 1) {
            // 더 높아지는 형태 -> map[y][x-1]이 X번 만큼 앞으로 연속적이어야 함
            for(int i = 1; i<X; i++){
                if(x-1-i < 0) {
                    // 앞에 충분한 공간이 없음
                    return 0;
                }
                if(tmp[x-1] != tmp[x-1-i]){
                    // 충분한 평지가 없음
                    return 0;
                }
                else{
                    if(used[x-1-i] == 1){
                        return 0;
                    }
                }
            }
        }else if(tmp[x-1] - tmp[x] == 1) {
            // 더 낮아지는 형태 -> map[y][x]가 X번 만큼 뒤로 연속적이어야 함
            for(int i = 1; i<X; i++){
                if(x+i >= N) {
                    // 뒤에 충분한 공간이 없음
                    return 0;
                }
                if(tmp[x] != tmp[x+i]){
                    // 충분한 평지가 없음
                    return 0;
                }   
            }
            // 충분한 평지가 있었음
            for(int i = 0; i<X; i++){
                used[x+i] = 1;
            }
        }
        else{
            // 차이가 2 이상
            return 0;
        }
    }
    return 1;
    
}

int Solve(void){

    int cnt = 0;

    // 가로 활주로 확인
    for(int y = 0; y<N; y++)
    {   
        for(int i = 0; i<N; i++){
            tmp[i] = map[y][i];
        }
        cnt+= check();
    }
    // 세로 활주로 확인
    for(int x = 0; x<N; x++)
    {
        for(int i = 0; i<N; i++){
            tmp[i] = map[i][x];
        }
        cnt+= check();
    }

    return cnt;

}

int main(void){

    int ans;
    // 입력받기
    scanf("%d", &T);
    for(int i = 0; i<T; i++){
        // 각 테이스 케이스별 풀이
        getInput();
        ans = Solve();
        printf("#%d %d\n", i+1, ans);
    }    

    return 0;
}