[SWEA] 4014. 활주로 건설

문제 접근

1. 시뮬레이션 문제이다.
   문제 조건에 맞게 코드를 짜면 됨. 슬로퍼가 놓일 수 있는 다양한 경우의 수가 있는데 이를 규칙을 찾아 단순화 하는 것이 중요하다.
2. 알고리즘
   절벽지대의 정보를 입력 받아 활주로를 건설할 수 있는지 여부를 판단하게끔 하였다. 이때 가로, 세로의 절벽 지대롤 하나의 1차원 배열에 복사하여 문제를 풀었다. (가로, 세로를 별도로 고려하지 않아도 되기 때문)

• 절벽지대의 높이가 2 이상 차이가 날 경우: 활주로를 건설할 수 없다.

• 1 차이가 날 경우: 오르막 슬로퍼(lslope)를 설치해야 할 경우, 내리막 슬로퍼(rslope)를 설치해야 할 경우로 나누어 슬로퍼를 설치할 수 있는지 평가하였다.

  • lslope(map[x] < map[x + 1]): x부터 시작하여 왼쪽으로 X개의 평지가 있고, 그곳에 슬로퍼를 놓을 수 있는지 확인
  • rslope(map[x] > map[x + 1]): x + 1부터 시작하여 오른쪽으로 X개의 평지가 있고, 그곳에 슬로퍼를 놓을 수 있는지 확인

3. lsople와 rslope에 겹치는 구간이 있다면 활주로를 건설할 수 없으므로 false를 return한다.

풀이

#include <iostream>
#include <cmath>
using namespace std;

int T, N, X, rst;
int map[20][20];

void input() {
    cin >> N >> X;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    rst = 0;
}

int is_range(int x) {
    if (x >= 0 && x < N) return true;
    return false;
}

int check(int map[]) {
    int lslope[20] = {0, };
    int rslope[20] = {0, }; 

    for(int x = 0; x < N - 1; x++){
        if(abs(map[x] - map[x + 1]) >= 2) return false;
    }

    for(int x = 0; x < N - 1; x++){
        if(map[x] == map[x + 1]) continue;

        if(map[x] < map[x + 1]){ // left slope
            for(int i = 0; i < X; i++){
                int nx = x - i;
                if(!is_range(nx) || map[x] != map[nx] || lslope[nx]) return false;
            }
            for(int i = 0; i < X; i++){
                int nx = x - i;
                lslope[nx] = 1;
            }
        }
        else { // right slope: map[x] > map[x + 1]
            for(int i = 1; i <= X; i++){
                int nx = x + i;
                if(!is_range(nx) || map[x + 1] != map[nx] || rslope[nx]) return false;
            }
            for(int i = 1; i <= X; i++){
                int nx = x + i;
                rslope[nx] = 1;
            }
        }
    }
    for(int i = 0; i < N; i++){
        if(rslope[i] && lslope[i]) return false;
    }
    return true;
}

void solve() {
    int idx, input[20];
    for (int i = 0; i < N; i++) {
        idx = 0;
        for (int j = 0; j < N; j++) {
            input[idx++] = map[i][j];
        }
        if (check(input)) rst++;
    }
    for (int i = 0; i < N; i++) {
        idx = 0;
        for (int j = 0; j < N; j++) {
            input[idx++] = map[j][i];
        }
        if (check(input)) rst++;
    }
}

int main() {
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        input();
        solve();
        cout << "#" << tc << " " << rst << endl;
    }
}

X개의 '평지' 조건을 확인하지 않았는데 문제는 통과되었다. 문제 접근법 쓰면서 알게 되어서 수정.