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

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

---

1. 이해하기

• 활주로는 높이가 동일한 구간에서 건설이 가능하다.
• 높이가 다른 구간의 경우 활주로가 끊어지기 때문에 길이가 X이고, 높이가 1인 경사로를 설치해야만 한다.
• 경사로는 경사로의 길이만큼 활주로의 높이가 같아야 설치가 가능하다.
• 동일한 위치에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.
• 경사로는 세워서 사용할 수 없다.

---

2. 구현하기

• 각 활주로마다 경사로를 설치할 수 있는지 확인한다.

  • 활주로에 경사로가 설치가 이미 되어있는지 확인.
  • 경사로의 길이만큼 활주로의 높이가 같은지 확인.

  bool is_installed(bool install[20], int st, int en) {
      for(int i = st; i <= en; i++) {
          if(install[i]) return true;
      }
      return false;
  }
  
  bool is_same_height_row(int row, int st, int en) {
      int height = map[row][st];
      for(int i = st; i <= en; i++) {
          if(height != map[row][i]) return false;
      }
      return true;
  }
  
  bool can_install_row(bool install[20], int row, int st, int en) {
      if(is_installed(install,st,en)) return false;
      if(!is_same_height_row(row,st,en)) return false;
      return true;
  }
  
  void install_way(bool install[20], int st, int en) {
      for(int i = st; i <= en; i++) {
          install[i] = true;
      }
  }
  
  bool is_same_height_col(int col, int st, int en) {
      int height = map[st][col];
      for(int i = st; i <= en; i++) {
          if(height != map[i][col]) return false;
      }
      return true;
  }
  
  bool can_install_col(bool install[20], int col, int st, int en) {
      if(is_installed(install,st,en)) return false;
      if(!is_same_height_col(col,st,en)) return false;
      return true;
  }

• 각 행과 열에 대해서 활주로가 될 수 있는지 검사한다.

  int solve() {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          bool flag = true;
          bool install[20] = {false,};
          for(int j = 0; j < N-1; j++) {
              if(map[i][j]+1 < map[i][j+1] or map[i][j] > map[i][j+1]+1) {
                  flag = false; break;
              } else if(map[i][j]+1 == map[i][j+1]) {
                  int st = j-X+1, en = j;
                  if(st < 0) {
                      flag = false; break;
                  }
                  if(!can_install_row(install,i,st,en)) {
                      flag = false; break;
                  } else {
                      install_way(install,st,en);
                  }
              } else if(map[i][j] == map[i][j+1]+1) {
                  int st = j+1, en = j+X;
                  if(en >= N) {
                      flag = false; break;
                  }
                  if(!can_install_row(install,i,st,en)) {
                      flag = false; break;
                  } else {
                      install_way(install,st,en);
                  }
              }
          }
          if(flag) ret++;
          memset(install,false,sizeof(install));
          flag = true;
          for(int j = 0; j < N-1; j++) {
              if(map[j][i]+1 < map[j+1][i] or map[j][i] > map[j+1][i]+1) {
                  flag = false; break;
              } else if(map[j][i]+1 == map[j+1][i]) {
                  int st = j-X+1, en = j;
                  if(st < 0) {
                      flag = false; break;
                  }
                  if(!can_install_col(install, i, st, en)) {
                      flag = false; break;
                  } else {
                      install_way(install,st,en);
                  }
              } else if(map[j][i] == map[j+1][i]+1) {
                  int st = j+1, en = j+X;
                  if(en >= N) {
                      flag = false; break;
                  }
                  if(!can_install_col(install,i,st,en)) {
                      flag = false; break;
                  } else {
                      install_way(install,st,en);
                  }
              }
          }
          if(flag) ret++;
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <cstring>
using namespace std;
int map[20][20];
int N,X;

bool is_installed(bool install[20], int st, int en) {
    for(int i = st; i <= en; i++) {
        if(install[i]) return true;
    }
    return false;
}

bool is_same_height_row(int row, int st, int en) {
    int height = map[row][st];
    for(int i = st; i <= en; i++) {
        if(height != map[row][i]) return false;
    }
    return true;
}

bool can_install_row(bool install[20], int row, int st, int en) {
    if(is_installed(install,st,en)) return false;
    if(!is_same_height_row(row,st,en)) return false;
    return true;
}

void install_way(bool install[20], int st, int en) {
    for(int i = st; i <= en; i++) {
        install[i] = true;
    }
}

bool is_same_height_col(int col, int st, int en) {
    int height = map[st][col];
    for(int i = st; i <= en; i++) {
        if(height != map[i][col]) return false;
    }
    return true;
}

bool can_install_col(bool install[20], int col, int st, int en) {
    if(is_installed(install,st,en)) return false;
    if(!is_same_height_col(col,st,en)) return false;
    return true;
}

int solve() {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        bool flag = true;
        bool install[20] = {false,};
        for(int j = 0; j < N-1; j++) {
            if(map[i][j]+1 < map[i][j+1] or map[i][j] > map[i][j+1]+1) {
                flag = false; break;
            } else if(map[i][j]+1 == map[i][j+1]) {
                int st = j-X+1, en = j;
                if(st < 0) {
                    flag = false; break;
                }
                if(!can_install_row(install,i,st,en)) {
                    flag = false; break;
                } else {
                    install_way(install,st,en);
                }
            } else if(map[i][j] == map[i][j+1]+1) {
                int st = j+1, en = j+X;
                if(en >= N) {
                    flag = false; break;
                }
                if(!can_install_row(install,i,st,en)) {
                    flag = false; break;
                } else {
                    install_way(install,st,en);
                }
            }
        }
        if(flag) ret++;
        memset(install,false,sizeof(install));
        flag = true;
        for(int j = 0; j < N-1; j++) {
            if(map[j][i]+1 < map[j+1][i] or map[j][i] > map[j+1][i]+1) {
                flag = false; break;
            } else if(map[j][i]+1 == map[j+1][i]) {
                int st = j-X+1, en = j;
                if(st < 0) {
                    flag = false; break;
                }
                if(!can_install_col(install, i, st, en)) {
                    flag = false; break;
                } else {
                    install_way(install,st,en);
                }
            } else if(map[j][i] == map[j+1][i]+1) {
                int st = j+1, en = j+X;
                if(en >= N) {
                    flag = false; break;
                }
                if(!can_install_col(install,i,st,en)) {
                    flag = false; break;
                } else {
                    install_way(install,st,en);
                }
            }
        }
        if(flag) ret++;
    }
    return ret;
}

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

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << solve() << '\n';
    }
    return 0;
}