[SWEA][C++] 4014 활주로 건설

[SWEA][C++] 4014 활주로 건설

 

문제

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

 

풀이

문제에서 주어진 조건들을 모두 충족시키도록 코드를 구현했습니다. 

우선, col과 row 고정을 하여 두가지 과정으로 분리하였습니다. 이후, 현재 층과 다음 층을 비교하여 다음 층이 큰 경우와 작은 경우, 다음 층과 같은 경우, 2층 이상 차이나는 경우로 나누었습니다. 

다음 층이 작은 경우, 범위를 체크하고 높이가 다음 층과 X의 범위 안에 들어오는 배열 값들을 비교해줍니다. 이 때, 활주로를 세웠다는 것을 possible배열을 이용해 체크합니다. 조건 충족이 안될 경우 isOK를 true로 바꿉니다.

다음 층이 큰 경우, 범위 체크 후 현재 층과 X의 범위 안의 값들을 비교하고 활주로가 세워졌는지 possible 배열을 통해 확인합니다. 조건 충족이 안될 경우 isOK를 true로 바꿉니다.

다음 층과 같을 경우 continue로 넘어가고, 다음 층과 2층 이상 차이 날 경우 isOK변수를 true로 바꾸고 for문을 빠져나갑니다. 

한 줄을 마치고 isOK변수가 false일 경우 result값을 증가시켜줍니다.

추가로 코드를 고치다보니 코드가 지저분하네요ㅠㅠ다음에는 더 빨리 풀어야지.... (5시간 걸린건 안비밀...)

 

코드

#include <iostream>
using namespace std;
int N, X;
int **arr;

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        /* t번째 케이스 시작 */
        cin >> N >> X;

        /* n크기의 동적 배열 생성 */
        arr = new int*[N];
        for (int n = 0; n < N; n++) {
            arr[n] = new int[N];
        }
        /* 배열 값 입력 받기 */
        for (int p = 0; p < N; p++) {
            for (int q = 0; q < N; q++) {
                cin >> arr[p][q];
            }
        }
        int result = 0;
        int *possible;

        /* (row고정) 다음 층이 높은 층? 낮은 층? 인지 알아보기 */
        for (int i = 0; i < N; i++) {
            possible = new int[N];
            fill_n(possible, N, 0);
            int isOK = false;
            for (int j = 0; j < N-1; j++) {

                /*현재 층*/
                int now = arr[i][j];
                /*다음 층*/
                int next = arr[i][j+1];


                /*다음 층이 큰 경우*/
                if (next - now == 1 ) {
                    /*j부터 (j+1)-(x)까지 같은 층인지 확인*/

                    /* 범위초과 경우 break */
                    if ((j + 1) - X < 0) {
                        isOK = true;
                        break;
                    }
                    for (int x = 1; x <= X; x++) {
                        /*높이 확인*/
                        if (arr[i][(j+1) - x] == now) {
                            /*이미 세웠는지 확인*/
                            if(possible[(j + 1) - x] == 0)
                                /*활주로 가능*/
                                continue;
                            else {
                                isOK = true;
                                break;
                            }

                        }
                        /*아닐 경우 break*/    
                        else{
                            isOK = true;
                            break;
                        }
                    }                
                }


                /*다음 층이 작은 경우*/
                else if(next - now == -1){
                    /*범위 초과 break*/
                    if (j + X >= N) {
                        isOK = true;
                        break;
                    }    
                    for (int x = 1; x <= X; x++) {
                        /*높이 확인*/
                        if (arr[i][j + x] == next) {
                            //활주로 세움 표시
                            possible[j + x] = 1;
                            continue;
                        }
                        else {
                            isOK = true;
                            break;
                        }
                            
                    }
                }
                /*다음층과 같을 경우*/
                else if (next - now == 0){
                    continue;
                }
                /*다음 층과 2이상 차이가 날 경우*/
                else {
                    isOK = true;
                }

                if (isOK == true) break;

            }
            if (isOK == false) {
                ++result;
            }

        }
        
        /* (col고정) 다음 층이 높은 층? 낮은 층? 인지 알아보기*/
        for (int i = 0; i < N; i++) {
            possible = new int[N];
            fill_n(possible, N, 0);
            int isOK = false;
            for (int j = 0; j < N - 1; j++) {

                /*현재 층*/
                int now = arr[j][i];
                /*다음 층*/
                int next = arr[j+1][i];


                /*다음 층이 큰 경우*/
                if (next - now == 1) {
                    /*범위 확인*/
                    if ((j + 1) - X < 0) {
                        isOK = true;
                        break;
                    }
                    for (int x = 1; x <= X; x++) {
                        /*높이 확인*/
                        if (arr[(j + 1) - x][i] == now) {
                            if (possible[(j + 1) - x] == 0) {
                                continue;
                            }
                            else {
                                isOK = true;
                                break;
                            }
                            
                        }
                        /*아닐 경우 break*/    
                        else {
                            isOK = true;
                            break;
                        }
                    }
                }
                /*다음 층이 작은 경우*/
                else if (next - now == -1) {
                    /*범위 확인*/
                    if (j + X >= N) {
                        isOK = true;
                        break;
                    }
                    
                    for (int x = 1; x <= X; x++) {
                        /*높이 확인*/
                        if (arr[j + x][i] == next) {
                            possible[j + x] = 1;
                            continue;
                        }
                        else {
                            isOK = true;
                            break;
                        }

                    }
                }
                /*다음층과 같을 경우*/
                else if (next - now == 0) {
                    continue;
                }
                /*다음 층과 2이상 차이가 날 경우*/
                else {
                    isOK = true;
                }

                if (isOK == true) break;

            }
            if (isOK == false) {
                ++result;
            }

        }
        
        cout << "#" << t+1 << " " << result << endl;


    }
    return 0;
}