[C++] 백준/Gold/14890. 경사로

문제: 경사로 (백준 14890번)

문제 분석

n×n 크기의 지도에서 각 칸의 높이가 주어지고, 경사로를 설치할 수 있는 조건에 맞춰 길(행 또는 열) 중 지나갈 수 있는 길의 개수를 구하는 빡구현 문제이다.

1. 높이 차이가 2 이상이면 해당 길은 지나갈 수 없다.
2. 높이 차이가 1일 경우,
   • 오르막: 바로 이전 칸들이 l칸 이상 연속해서 동일한 높이여야 경사로를 설치할 수 있다.
   • 내리막: 앞으로 l칸이 모두 현재 칸과 같은 낮은 높이여야 하며, 해당 칸에 이미 경사로가 설치되지 않아야 한다.
3. 경사로는 한 번만 설치 가능하다.

---

해결 방법

함수 설계:

• checkRow 함수는 주어진 행 또는 열이 조건에 맞게 경사로를 설치할 수 있는지를 판단한다.
• 매개변수:
  • vector<vector<int>>& v: 지도 정보
  • s, e: 시작과 끝 인덱스
  • row: 검사할 행 번호(혹은 열 번호)
  • isRow: 행 검사인지, 열 검사인지를 구분하는 플래그

검사 로직:

• 기본 변수:
  • prev: 이전 칸의 높이
  • cnt: 현재 연속해서 같은 높이인 칸의 개수
  • placed: 경사로가 이미 설치된 위치를 표시하는 불리언 배열
• 오르막 상황:
  • 현재 칸의 높이가 이전 칸보다 1 높다면, 그 이전에 l개의 연속된 칸이 있어야 하며, 해당 칸에 경사로가 없으면 설치한다.
• 내리막 상황:
  • 현재 칸의 높이가 이전 칸보다 1 낮다면, 앞으로 l칸이 모두 현재 칸과 같은 높이여야 하며, 경사로가 설치되지 않아야 한다. 설치 후에는 인덱스를 l칸만큼 건너뛴다.
• 동일 높이:
  • 연속된 칸의 개수 cnt를 증가시켜 다음 설치 가능 여부를 판단한다.

• 전체 흐름:
  1. 입력으로 n, l과 지도 정보를 받는다.
  2. 각 행과 각 열에 대해 checkRow 함수를 호출하여 지나갈 수 있는 길인지 판별한다.
  3. 조건에 맞는 길의 총 개수를 출력한다.

코드 전체

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

int n, l;

bool checkRow(vector<vector<int>>& v, int s, int e, int row, bool isRow)
{
    vector<bool> placed(n, false); // 경사로 설치 여부
    int prev = isRow ? v[row][s] : v[s][row], cnt = 1;

    for (int i = s + 1; i < e; i++)
    {
        int num = isRow ? v[row][i] : v[i][row];

        if (abs(num - prev) > 1) return false; // 높이 차이가 2 이상이면 불가능

        if (num > prev) // 오르막 경사로 설치 필요
        {
            if (cnt < l) return false; // 충분한 공간이 없음

            for (int j = i - l; j < i; j++)
            {
                if (placed[j]) return false; // 이미 경사로가 설치된 곳이면 불가능
                placed[j] = true;
            }
            cnt = 1; // 새로운 숫자가 시작되므로 초기화
        }
        else if (num < prev) // 내리막 경사로 설치 필요
        {
            if (i + l - 1 >= e) return false; // 범위를 벗어나면 불가능

            for (int j = i; j < i + l; j++)
            {
                if (isRow && v[row][j] != num) return false; // 같은 높이인지 확인
                if (!isRow && v[j][row] != num) return false;
                if (placed[j]) return false; // 이미 경사로 설치된 곳이면 불가능
                placed[j] = true;
            }
            i += l - 1; // 경사로를 설치한 끝까지 이동
            cnt = 0; // 경사로 설치 완료
        }
        else cnt++; // 같은 숫자가 반복되면 cnt 증가

        prev = num;
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    cin >> n >> l;
    vector<vector<int>> v(n, vector<int>(n));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];

    int result = 0;
    // 각 행과 각 열을 검사
    for (int i = 0; i < n; i++)
    {
        result += checkRow(v, 0, n, i, true);
        result += checkRow(v, 0, n, i, false);
    }

    cout << result;
}