[백준] 14890번 경사로

14890번 경사로

---

1. 이해하기

• 지도에서 지나갈 수 있는 길이 몇개인지 세는 문제이다.
• 지나갈 수 있는 길은 평평한 길이거나 경사로를 설치할 수 있는 길을 의미한다.
  • 경사로는 높이 차이가 1인 곳, 경사로의 길이 만큼의 평평한 길이 있을 때만 설치할 수 있다.
  • 경사로를 이미 설치한 곳에 또 설치를 할 수 없다.
• 시뮬레이션 문제.

---

2. 구현하기

• 행과 열의 특정 길이에 대해 경사로를 설치할 수 있는지 판단한다. 설치할 수 있으면 설치한다.

  bool can_install_row(int i, int st, int en) {
      int temp = map[i][st];
      for(int j = st; j <= en; j++) {
          if(temp != map[i][j]) return false;
          if(installed[i][j][0]) return false;
      }
      return true;
  }
  
  void install_row(int i, int st, int en) {
      for(int j = st; j <= en; j++) {
          installed[i][j][0] = true;
      }
  }
  
  bool can_install_col(int i, int st, int en) {
      int temp = map[st][i];
      for(int j = st; j <= en; j++) {
          if(temp != map[j][i]) return false;
          if(installed[j][i][1]) return false;
      }
      return true;
  }
  
  void install_col(int i, int st, int en) {
      for(int j = st; j <= en; j++) {
          installed[j][i][1] = true;
      }
  }

• 모든 구간을 둘러보며 경사로가 설치 될 수 있을 만한 구간을 찾고 지나갈 수 있는 곳이면 ret의 수를 늘린다.

  int solve() {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          bool flag = true;
          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;
              }
              if(map[i][j]+1 == map[i][j+1]) {
                  int st = j-L+1, en = j;
                  if(st < 0) {
                      flag = false; break;
                  }
                  if(!can_install_row(i,st,en)) {
                      flag = false; break;
                  }
                  install_row(i,st,en);
              } else if(map[i][j] == map[i][j+1]+1) {
                  int st = j+1, en = j+L;
                  if(en >= N) {
                      flag = false; break;
                  }
                  if(!can_install_row(i,st,en)) {
                      flag = false; break;
                  }
                  install_row(i,st,en);
              }
          }
          if(flag) ret++;
          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;
              }
              if(map[j][i]+1 == map[j+1][i]) {
                  int st = j-L+1, en = j;
                  if(st < 0) {
                      flag = false; break;
                  }
                  if(!can_install_col(i,st,en)) {
                      flag = false; break;
                  }
                  install_col(i,st,en);
              } else if(map[j][i] == map[j+1][i]+1) {
                  int st = j+1, en = j+L;
                  if(en >= N) {
                      flag = false; break;
                  }
                  if(!can_install_col(i,st,en)) {
                      flag = false; break;
                  }
                  install_col(i,st,en);
              }
          }
          if(flag) ret++;
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
int map[100][100];
bool installed[100][100][2];
int N,L;

bool can_install_row(int i, int st, int en) {
    int temp = map[i][st];
    for(int j = st; j <= en; j++) {
        if(temp != map[i][j]) return false;
        if(installed[i][j][0]) return false;
    }
    return true;
}

void install_row(int i, int st, int en) {
    for(int j = st; j <= en; j++) {
        installed[i][j][0] = true;
    }
}

bool can_install_col(int i, int st, int en) {
    int temp = map[st][i];
    for(int j = st; j <= en; j++) {
        if(temp != map[j][i]) return false;
        if(installed[j][i][1]) return false;
    }
    return true;
}

void install_col(int i, int st, int en) {
    for(int j = st; j <= en; j++) {
        installed[j][i][1] = true;
    }
}

int solve() {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        bool flag = true;
        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;
            }
            if(map[i][j]+1 == map[i][j+1]) {
                int st = j-L+1, en = j;
                if(st < 0) {
                    flag = false; break;
                }
                if(!can_install_row(i,st,en)) {
                    flag = false; break;
                }
                install_row(i,st,en);
            } else if(map[i][j] == map[i][j+1]+1) {
                int st = j+1, en = j+L;
                if(en >= N) {
                    flag = false; break;
                }
                if(!can_install_row(i,st,en)) {
                    flag = false; break;
                }
                install_row(i,st,en);
            }
        }
        if(flag) ret++;
        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;
            }
            if(map[j][i]+1 == map[j+1][i]) {
                int st = j-L+1, en = j;
                if(st < 0) {
                    flag = false; break;
                }
                if(!can_install_col(i,st,en)) {
                    flag = false; break;
                }
                install_col(i,st,en);
            } else if(map[j][i] == map[j+1][i]+1) {
                int st = j+1, en = j+L;
                if(en >= N) {
                    flag = false; break;
                }
                if(!can_install_col(i,st,en)) {
                    flag = false; break;
                }
                install_col(i,st,en);
            }
        }
        if(flag) ret++;
    }
    return ret;
}

int main() {
    cin >> N >> L;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }

    cout << solve() << '\n';
    return 0;
}