[BOJ] 14890. 경사로

[문제]

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

14890번: 경사로

[풀이]

 

1) 현재 칸과 다음 칸이 다를 때와 같을 때로 나뉜다. 

 

2) 행과 열을 모두 탐색할 때 단순하게 모두 행으로 붙여준다. map[n*2][n]

 

3) 나올 수 있는 모든 경우의 수 (n*2)를 초기값으로 두고 경사로를 설치할 수 없는 경우이거나 높이의 차가 1이상인 경우를 제거해간다. 

 

4) 행의 수만큼 (n*2)만큼 반복하면서 길을 찾는다. 

 

5) 먼저 최고 높이가 10이하이므로 height 배열을 11의 크기만큼 만들어준다. 

height 배열은 각 칸의 높이가 같은 칸이 얼마나 존재하는지 저장한다. (연속된 칸들만)

 

6) 지정 행에서 가장 먼저 오는 칸을 기준으로 삼는다. (stand)

height[stand]  = 1

stand 다음 칸은 next로 지정한다.

 

7) stand != next 일 때 세 가지 경우가 있다. 

 

• 현재 칸과 다음 칸의 높이 차가 1이상인 경우 (절대값으로 계산해야 한다.) => 경사로 형성 불가

• 현재 칸이 다음 칸보다 낮은 경우 -> 현재까지 지나온 칸들 중 현재 칸과 같은 높이의 칸이 l 이상이어야 한다. 

• 현재 칸이 다음 칸보다 높은 경우 -> 앞으로 나올 칸들 중 다음 칸과 같은 높이의 칸이 l 이상이어야 한다. 

8) stand == next 

height[stand] ++ (지금까지 지나온 칸들 중 stand와 같은 칸들의 카운트 수 증가)

 

---

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
 
int n, l, map[101*2][101]; //l : 경사로의 길이 (높이는 1)
int height[11]; //각 높이를 저장 (높이는 최대 10)
 
int findPath() {
    //시뮬레이션 
    int ans = 0;
    for (int i = 0; i < n*2; i++) {
        bool flag = true;
 
        memset(height, 0, sizeof(height));
 
        int stand = map[i][0];
        height[stand] = 1;
 
        for (int j = 1; j < n; j++) {
            //맨 앞 인덱스의 높이와 그 다음 인덱스의 높이가 1이 나면 l만큼의 같은 높이가 연속되는지 확인한다. 
            //만약 길의 모든 높이가 같으면 ans++;
            
            int next = map[i][j]; //기준 칸 다음 칸 
            
            if (stand != next) {
                if (abs(stand - next) > 1) {
                    //경사로 형성 불가 
                    flag = false;
                    break;
                }
                else if (abs(stand - next) == 1) {
                    if (stand > next) {
                        //l만큼 같은 높이의 길이 있어야 함 
                        for (int k = j; k < j + l && k < n; k++) {
                            if (map[i][k] == next)
                                height[next]++;
                        }
                        if (height[next] < l) {
                            flag = false;
                            break;
                        }
                        height[next] -= l; //임의로 늘려준 거니까 다시 빼준다. 
                        j += l-1; //l길이만큼 앞으로 이동 (경사로가 놓였으니 더 볼 필요 없다.)
                    }
                    else {
                        if (height[stand] < l) {
                            flag = false;
                            break;
                        }
                        height[stand] = 0; //이번 경사로에 대한 진위 판단이 끝났으니 다음 칸의높이를 고려한다. 
                        height[next] = 1;
                    }
                }
                //다음칸의 높이를 기준으로 삼는다. 
                stand = next; 
            }
            else {
                //높이가 같을 때 
                height[stand]++;    
            }
        }//for j
        if (flag) ans++; //지나갈 수 있는 길  
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> l;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    //input 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[n+i][j] = map[j][i];
        }
    }
 
    cout << findPath() << '\n';
 
    return 0;
}