[알고리즘] 백준 14890 경사로 // 구현, 전치행렬이용, cnt 이용법

https://www.acmicpc.net/problem/14890

* 문제 해결 방식

1. 문제 단순화하기
2. 처음에는 "한 줄"만 생각합니다. - 가로 한 줄에서 경사로를 어떻게 놓을 수 있을까? - 어떤 조건에서 경사로를 놓을 수 있고, 없을까?
3. 상태 추적하기
4. 현재 상황을 추적할 변수가 필요함을 깨닫습니다. - 같은 높이가 몇 칸 연속되는지 - 경사로를 놓고 있는 중인지 => 이 두 가지를 하나의 변수(cnt)로 표현할 수 있다!
5. 패턴 발견하기
6. 높이 차이에 따른 패턴을 분석합니다: 1. 같은 높이: 여유분 증가 2. 오르막: 이전 여유분 필요 3. 내리막: 앞으로의 공간 필요
7. 최적화하기
8. 가로/세로 방향 체크를 같은 로직으로 처리하려면? => 전치행렬을 사용하면 동일한 함수로 처리 가능!
9. 엣지 케이스 생각하기
10. - 연속된 경사로가 필요한 경우 - 마지막 칸까지 완성해야 하는 경우 - 높이 차이가 2 이상인 경우

💡 핵심 통찰

• 하나의 변수(cnt)로 두 가지 상태(여유분/필요분)를 표현
• 양수/음수를 통해 상태의 의미를 다르게 해석
• 전치행렬로 코드 재사용

이런 사고방식을 기르려면:

1. 작은 예시부터 시작하여 패턴 발견
2. 상태를 추적하는 다양한 방법 고민
3. 코드를 더 단순하게 만들 방법 지속적으로 고민
4. 여러 테스트 케이스를 만들어보며 검증

 

* 아이디어

• 전치행렬을 통해 solve 함수 1개만으로 날먹해야함

입력받을때 b 행렬을 만들어 놓기만 하면됨

• solve 함수내에 오르막, 내리막인 경우를 여기서 구현 ( <- 역방향 탐색 필요X )
• 오르막인경우 해보기
  • 높이가 같으면 cnt 증가 => 경사로 공사할 공간 확보
  • 오르막이면, 확보한공간(cnt)이 충분한지(L이상인지) 확인 -> cnt=1로 다시시작

• 내리막인경우
  • 이때, cnt를 음수로 둠 (앞으로 필요한 칸 수(-L+1) 카운트 시작)

얘때문에 cnt>=0 검사 필요

* 코드

의사코드:

// 메인 함수
MAIN:
    입력: N(지도 크기), L(경사로 길이)
    2차원 배열 a[N][N] 입력받기
    2차원 배열 b[N][N]을 a의 전치행렬로 만들기 // 세로방향 체크용

    경로체크(a) 실행  // 가로방향 체크
    경로체크(b) 실행  // 세로방향 체크

    결과 출력

// 경로 체크 함수
경로체크(배열):
    각 행(i = 0 to N-1)에 대해:
        cnt = 1  // 현재 연속된 같은 높이의 수

        각 열(j = 0 to N-2)에 대해:  // 현재칸과 다음칸 비교
            현재칸 = a[i][j]
            다음칸 = a[i][j+1]

            IF 현재칸 == 다음칸:
                cnt++  // 같은 높이가 연속되면 여유분 증가

            ELSE IF 현재칸 + 1 == 다음칸 AND cnt >= L:
                // 오르막길 && 경사로를 놓을 만큼의 여유가 있음
                cnt = 1  // 새로운 높이에서 카운트 시작

            ELSE IF 현재칸 - 1 == 다음칸 AND cnt >= 0:
                // 내리막길 && 현재 진행중인 경사로가 없음
                cnt = -L + 1  // 앞으로 필요한 칸 수 카운트 시작

            ELSE:
                다음 행으로 이동  // 불가능한 경우

        IF cnt >= 0 AND 마지막까지 도달:
            가능한 경로 수 증가

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

int n,L,ret;
int a[104][104], b[104][104];

void go(int a[104][104]) {
    for(int i=0;i<n;++i) {
        int cnt=1;
        int j; // 마지막에 조회 필요
        for(j=0;j<n-1;++j) {
            // 높이가 같은경우, cnt를 증가(여유분 확보)
            if(a[i][j]==a[i][j+1]) {
                cnt++;
            }
            //오르막인경우 && 경사를 놓을만큼 여유분이 있음
            //경사로를 놓고 새로 카운팅 시작
            else if(a[i][j]+1 == a[i][j+1] && cnt >= L) {
                cnt=1;
            }
            //내리막인경우 && 내리막이 연속으로 나오는경우는 제외
            //필요한 경사로 카운팅 시작
            else if(a[i][j]-1 == a[i][j+1] && cnt >= 0) {
                cnt=-L+1;
            }
            else break;
        }
        // 경사로를 설치할만큼 여유가 되고, 마지막 까지 온경우
        if(cnt>=0 && j==n-1) ret++;
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>L;

    for(int i=0;i<n;++i) {
        for(int j=0;j<n;++j) {
            cin>>a[i][j]; // r,c 아님에 주의!
            b[j][i]=a[i][j]; // 전치행렬 => 세로 날먹
        }
    }

    go(a), go(b);

    cout<<ret;

    return 0;
}