[구현 / BOJ 14890 / C++] 경사로

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

14890번: 경사로

1) 2차원 배열을 2개 만든다. 한가지는 대칭이동 시켜서 만든다.
2) 지금까지 지나온 같은 높이의 칸의 개수를 세준다.(cnt)
3) 만약 다른 높이의 칸을 만난다면,
3-1) cnt >= L 이고 +1 칸 차이이면 cnt = 1로 해준다.(오르막경사)
3-2) cnt >= 0 이고, -1 칸 차이이면, cnt = -L+1로 해준다 (내리막 경사)
3-3) 위에 해당하지 않으면 break 해주고 해당 열/행의 탐색을 종료한다.
4) 길을 찾았다면, res에 +1

이 문제는 단순하지만 구현이 복잡했다... 그래서 포기하고 해설을 봤는데 진짜 참신하게 풀어냈다.

 

우선 가장 큰 아이디어는

 

1) 행, 열을 따로 정리한 2가지 로직을 2차원 배열의 대칭이동을 통해 "1가지" 로직으로 해결한다.

 

2) 내리막길의 경우, 경사로를 놓을 수 없는 경우를 구할때, "음수" 표현을 사용한다.

 

이다. 바로 이해가 되지 않을 것이다. 다음 그림을 봐보자.

 

1번 로직은 위와 같이 기존의 2차원 배열을 대칭이동 시켜서 한가지 방향으로만 탐색할 수 있게 바꾸는 것이다...!

원래는 노랑 경우의 배열을 고려하면, 행 방향으로 {123, 456, 789} 탐색한 후 열방향으로 {147, 258, 369}로 표현해야하므로

로직 짜기가 번거롭다. 따라서 대칭이동시킨 배열을 하나 따로 만들어서, 행방향으로 문제를 해결하는 한가지 로직을 사용하는 것이다!

 

우선 문제 요구사항은 간단하다. 계속 같은 높이가 나오면 cnt을 늘려주면 되고, 만약 다른 높이칸을 만날 경우만을 처리해주면 된다.

이때, 두가지 경우의 수가 있다.

 

1) 오르막 경사를 만들어야하는 경우

이는 간단하다. cnt가 주어진 L 보다 크거나 같으면 된다. 위의 경우 L=3이라 가정할 경우, 지금까지 지나온 cnt가 3이므로

오르막 경사가 가능하다. 그리고나서 cnt=1로 해줘야한다.

 

2) 내리막 경사

여기가 조금 헷갈릴텐데, cnt를 -L+1로 설정하는 것이다. 그리고 처음 얘기한 로직대로 같은 높이의 칸을 만나면 계속 +1이 될 것이다.

이때, 0이되는 순간이 바로 경사로 길이(L)이 되는 것이다. 하지만, 같은 높이의 칸의 개수가 충분치 않다면 (cnt < 0), 이는 경사로를 놓을 수 없는 순간이다.

 

#include <bits/stdc++.h>

using namespace std;

int N, L, res;
int bd[110][110], cop[110][110];

void solve(int a[110][110]){
    for(int i = 0 ; i < N ; i++){
        int cnt = 1;
        
        int j;
        for(j = 0 ; j < N-1 ; j++){
            if(a[i][j] == a[i][j+1]) cnt++; // 같은 경우 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(j == N-1 && cnt >= 0) res++; // 끝까지 왔고, cnt는 음수가 아님.
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> L;
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> bd[i][j];
            cop[j][i] = bd[i][j]; // 대칭입력받기.
        }
    }
    
    solve(bd); solve(cop);
    
 

    cout << res;
}