[C++] BOJ 14890 - 경사로

BOJ 14890 - 경사로 (https://www.acmicpc.net/problem/14890)

 

01. 🔎 문제 탐색

NxN: 지도의 크기
L: 경사로의 길이
- 지도의 한 칸마다 높이가 주어짐
- 길이란? 한 행 또는 한 열을 의미 (따라서, 2N개의 길이 존재)

• 길을 지나기위해서
  • 높이가 같은 곳을 지나갈 수 있음
  • 높이가 다른 곳은 경사로를 놓아 높이 1의 차이는 극복 가능
    • 경사로의 높이는 항상 1이며, 길이는 L
• 경사로를 놓기 위해서
  
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 함
  • 낮은 칸의 높이는 같아야 함
  • L개의 연속된 칸이 경사로 바닥면과 닿아야 함
• 경사로를 놓을 수 없는 경우
  
  • 이미 경사로가 있는 곳
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닐 때
  • 낮은 지점의 높이가 모두 같지 않고, L의 길이만큼 연속되지 않았을 때
  • 경사로가 주어진 범위를 벗어났을 때

 

01-1. 가능한 시간 복잡도

• N의 최대가 100으로 시간 복잡도 O(N^3) 이하로 구현해야 함
• 각 행과 열에 대해 유효한 길인지 구하는 방식으로 시간 복잡도 O(2*N^2)으로 구현 가능

 

02. 📝 코드 설계하기

1. N과 L을 입력받고, NxN 범위 지도의 높이를 각각 입력
2. 각 행과 열에 대해 유효한 길인지 탐색
   1. 현재 높이와 다음 칸의 높이 차이를 계산
   2. 높이 차이가 0일 경우, 전진
   3. 높이 차이가 1일 경우, 현재 칸을 포함하여 L만큼 뒷 칸까지 진행 조건을 확인, 조건을 만족하지 않을 경우 반복을 멈추고 다음 길로 이동
      (조건: 유효한 범위인지, 현재 칸과 같은 높이인지, 경사로가 설치되지 않았는 지)
   4. 높이 차이가 -1일 경우, 다음 칸부터 L만큼 앞 칸까지 진행 조건을 확인, 조건을 만족하지 않을 경우, 반복을 멈추고 다음 길로 이동
      (조건: 유효한 범위인지, 다음 칸부터 같은 높이인지, 경사로가 설치되지 않았는 지)
3. 길 탐색이 끝까지 수행되었을 경우, 유효한 길 횟수에 +1

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, L;
  cin >> N >> L;
  vector<vector<int>> board(N, vector<int>(N));

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

  int count = 0;
  for(int i = 0; i < N; i++){
    bool is_valid = true;
    vector<bool> is_used(N, false);

    for(int j = 0; j < N - 1; j++){
      if(!is_valid) break;

      int diff = board[i][j + 1] - board[i][j];

      if(diff == 0) continue;
      else if(diff == 1){
        for(int k = 0; k < L; k++){
          int idx = j - k;
          if(idx < 0 || board[i][idx] != board[i][j] || is_used[idx]){
            is_valid = false;
            break;
          }
          is_used[idx] = true;
        }
      }
      else if(diff == -1){
        for(int k = 1; k <= L; k++){
          int idx = j + k;
          if(idx >= N || board[i][idx] != board[i][j+1] || is_used[idx]){
            is_valid = false;
            break;
          }
          is_used[idx] = true;
        }
        j += (L-1);
      }
      else {
        is_valid = false;
        break;
      }
    }

    if(is_valid) count++;
  }

  for(int i = 0; i < N; i++){
    bool is_valid = true;
    vector<bool> is_used(N, false);

    for(int j = 0; j < N - 1; j++){
      if(!is_valid) break;

      int diff = board[j + 1][i] - board[j][i];

      if(diff == 0) continue;
      else if(diff == 1){
        for(int k = 0; k < L; k++){
          int idx = j - k;
          if(idx < 0 || board[idx][i] != board[j][i] || is_used[idx]){
            is_valid = false;
            break;
          }
          is_used[idx] = true;
        }
      }
      else if(diff == -1){
        for(int k = 1; k <= L; k++){
          int idx = j + k;
          if(idx >= N || board[idx][i] != (board[j+1][i]) || is_used[idx]){
            is_valid = false;
            break;
          }
          is_used[idx] = true;
        }
        j += (L-1);
      }
      else {
        is_valid = false;
        break;
      }
    }

    if(is_valid) count++;
  }

  cout << count << "\n";

  return 0;
}