[SWEA] 4014. [모의 SW 역량테스트] 활주로 건설

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

SW Expert Academy

나는 그냥 문제에 나와있는대로 하나하나 처리를 해줬는데 다른 사람들의 풀이를 보니까 더 간단하게 풀었던데 나중에 보고 다시 공부해봐야겠다.

 

먼저 가로방향과 세로방향을 각각 구해줬다.

가로 방향을 구할 때는 모든 행에 대해서 각각의 열을 비교하였다.

1. j열과 j+1 의 높이가 같다면 다음 열의 비교로 넘어간다.
2. 높이 차이가 1보다 크다면 경사로를 놓을 수도 없으므로 해당 행에는 활주로 건설이 불가능하다.
3. 높이차이가 1이라면 경사로를 놓을 수 있는지 확인한다. 밑의 조건에 맞지 않는다면 flag를 false로 바꿔준다.
   1. 경사로의 길이 x만큼을 놓았을 때 범위를 넘어가지 않는지 확인.
   2. 경사로를 놓아줄 x만큼의 칸의 높이가 같은지 확인.
   3. 경사로를 놓을 자리에 이미 경사로가 놓여있지 않은지 확인.
4. 위의 조건을 모두 통과하였다면 경사로를 놓아줄 것인데 j가 j+1보다 컸다면 j+1부터 뒷쪽으로 경사로를 놓아주면 되고, 반대의 경우에는 j부터 앞쪽으로 경사로를 놓아주면 된다.
5.  
6. 행의 열 끝까지가는 동안 flag가 true라면 (위의 조건에서 한번도 걸리지 않았다면) 해당 행은 활주로를 건설할 수 있다.

위와 같은 방식으로 세로 방향도 행과 열을 바꿔서 구해주면된다. 

 

#include <iostream>
#include <cstring>
using namespace std;
 
int n, x, ans;
int map[20][20];
bool checkG[20][20];
bool checkS[20][20];
 
int checkGaro() {
    int cnt = 0;
 
    //모든 행을 검사
    for (int i = 0; i < n; i++) {
 
        bool flag = true;
        for (int j = 0; j < n - 1; j++) {
            //높이가 같으면 다음 칸으로 넘어간다
            if (map[i][j] == map[i][j + 1]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i][j + 1];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i][j + 1]) {
                //범위를 벗어나는 경우
                if (j + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j + 1; k < j + x; k++) {
                    //경사로를 놓을 자리의 높이가 같은지 검사
                    if (map[i][k] != map[i][k + 1]) {
                        flag = false;
                        break;
                    }
 
                }
 
                for (int k = j + 1; k < j + x + 1; k++) {
                    //경사로가 이미 놓여져있는지 검사
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j + 1; k < j + 1 + x; k++) {
                        checkG[i][k] = true;
                    }
                }
 
 
            }
            else {//뒷칸이 더 큰 경우
                //범위를 벗어나는 경우
                if (j + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = j; k > j + 1 - x; k--) {
                    if (map[i][k] != map[i][k - 1]) {
                        flag = false;
                        break;
                    }
                }
 
                for (int k = j; k > j - x; k--) {
                    if (checkG[i][k]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = j; k > j - x - 1; k--) {
                        checkG[i][k] = true;
                    }
                }
 
            }
 
            //활주로를 건설할 수 없다.
            if (!flag) break;
 
        }
 
        //이번행은 활주로를 건설할 수 있다.
        if (flag) cnt++;
 
    }
 
 
    return cnt;
 
}
 
 
int checkSero() {
    int cnt = 0;
 
    //모든 열을 검사
    for (int j = 0; j < n; j++) {
 
        bool flag = true;
        for (int i = 0; i < n - 1; i++) {
 
            if (map[i][j] == map[i + 1][j]) continue;
 
 
            //높이 차이를 구해준다.
            int tmp = map[i][j] - map[i + 1][j];
            if (tmp < 0) tmp = -tmp;
 
            //1보다 차이가 크면 경사로를 놓을 수 없으므로 해당 행은 활주로 건설 불가
            if (tmp > 1) {
                flag = false;
                break;
            }
 
 
            //앞쪽이 더 높은 경우 뒷쪽에 경사로 놔준다.
            if (map[i][j] > map[i + 1][j]) {
                //범위를 벗어나는 경우
                if (i + x >= n) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i + 1; k < i + x; k++) {
                    //높이가 같은지 검사
                    if (map[k][j] != map[k + 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i + 1; k < i + x + 1; k++) {
                    //이미 놓여져있는지 검사
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i + 1; k < i + 1 + x; k++) {
                        checkS[k][j] = true;
                    }
                }
 
 
            }
            else {
                //범위를 벗어나는 경우
                if (i + 1 - x < 0) {
                    flag = false;
                    break;
                }
 
                //경사로를 x만큼 놓을 수 있는지 검사
                for (int k = i; k > i + 1 - x; k--) {
                    if (map[k][j] != map[k - 1][j]) {
                        flag = false;
                        break;
                    }
 
                    
                }
 
                for (int k = i; k > i - x; k--) {
                    if (checkS[k][j]) {
                        flag = false;
                        break;
                    }
                }
 
                //검사를 통과했다면 경사로를 놓아준다.
                if (flag) {
                    for (int k = i; k > i - x - 1; k--) {
                        checkS[k][j] = true;
                    }
                }
 
            }
 
            if (!flag) break;
 
        }
 
        if (flag) cnt++;
 
    }
 
 
    return cnt;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 0;
        memset(checkG, false, sizeof(checkG));
        memset(checkS, false, sizeof(checkS));
 
        cin >> n >> x;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
        
 
        ans = checkGaro() + checkSero();
        
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
 
    return 0;
}