[ 백준 14890 ] 경사로 (C++)

백준의 경사로(14890) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 맵이 주어지고, 맵은 숫자들로 이루어져 있다.

- 이웃한 숫자의 차이가 (행은 행끼리 열은 열끼리) 1일 때, 경사로를 설치할 수 있는 조건에 부합하면 경사로 설치가 가능하다.

- 경사로를 설치할 수 있는 조건은

  1. 땅의 높이의 차이가 1이어야 한다. (2 이상이면 불가능)

  2. 경사로의 길이만큼 땅의 높이가 같아야 의미한다.

- 예를들어서 1 2 3 5 4 3 이라는 땅이 있고 경사로의 길이가 1이라고 생각해보자. (앞에서부터 순서대로 1번~6번)

  제일 처음 1번과 2번을 비교해보자. 1번땅의 높이는 1, 2번땅의 높이는 2로써차이가 1이기 때문에 1번 조건에 부합하게 된다.

  또한, 경사로의 길이가 1이기 때문에 1위에 경사로를 설치하면 1번과 2번 땅이 연결될 것이다.

  다음은 2번과 3번을 비교해보자. 이 경우 또한, 높이차이가 1이고, 경사로의 길이만큼 땅이 있으므로 설치가 가능하다.

  3번과 4번을 비교해보면 차이가 2이기 때문에 경사로 설치조건인 1번 조건에 적합하지 않으므로, 이 길은 길이 될 수 없다.

- 이런식으로 경사로를 설치해서 모두 연결될 수 있으면 이를 길이라고 표현하며, 총 길의 갯수를 출력하면 된다.

[ 문제풀이 ]

1. 이 문제는 4가지 조건문만 구현을 완벽하게 하면 된다.

  1. 연결된 땅의 길이가 같을 때                              ==> (1 1)과 같이 땅의 높이가 같음.

  2. 연결된 땅 중에서 앞에 땅의 높이가 1만큼 더 높을 때 ==> (2 1)과 같이 앞에 땅의 높이가 더 높음.

  3. 연결된 땅 중에서 뒤에 땅의 높이가 1만큼 더 높을 때 ==> (1 2)와 같이 뒤에 땅의 높이가 더 높음.

  4. 연결된 땅의 높이 차이가 2이상일 때                ==> (1 3)과 같이 차이가 2 이상.

  먼저 1번부터 설명을 해보겠다.

  1번의 경우, 딱히 구현해줄 내용이 없다. 경사로를 설치해야 되는 것도 아니고, 그냥 넘어가면 된다.

  하지만, 경사로의 길이가 2 이상일 때는 이 경우에 무언가를 해줘야 한다. (뒤에 설명)

  2번의 경우, 경사로를 내리막처럼 보이게 구현을 해줘야 한다. 이 부분을 구현하기 위해서는 경사로의 길이만큼 땅이 평평한지

  확인을 해줘야한다.

  예를들어서 땅의 높이가 2 1 2 1 로 주어지고 경사로의 길이가 2라고 가정해보자.

  1번 2와 2번 1에 의해서 조건 2번에 속하게 되고, 이 경우, 경사로의 길이(2) 만큼 1이 있지 않기 때문에 경사로 설치가 불가능하다.

  땅의 높이를 바꾸서 2 1 1 1 이라면 경사로의 길이만큼 1이 있으므로 경사로 설치가 가능할 것이다.

  이 부분을 구현해주면 된다.

  3번의 경우 오르막 처럼 보이는 경사로를 구현해야 하는데, 이 경우에는 이전의 길의 상태를 확인할 필요가 있다.

  예를 들어 1 1 2 2 , 경사로의 길이 = 2 라고 가정해보자.

  이 경우 경사로를 설치할 수 있다는 것을 직감적으론 알 것이다. 하지만 이 때 이전의 길의 상태를 알아야 하는데

  위에서 말한 '무언가' 가 이 부분이다. 본인은 이 경우를 위해서 연결된 땅의 길이가 같을 때 ++ 시켜주는 변수를 사용했다.

  (변수명 : Before_Road) 이 변수는 연결된 땅의 길이가 같을 때 ++ 되며, 처음 1에 의해서 1, 2번째 1에 의해서 ++되어서 2가 되있는

  상태일 것이다. 이 때, 땅의 높이가 2인 놈을 만나게 되면, 경사로의 길이와 이 변수의 값을 비교해보면 된다.

  만약 이 변수 값이 경사로의 길이보다 크거나 같다면 경사로 설치가 가능하고, 아니라면 불가능 한 것이다.

  이렇게 값을 비교하고 경사로를 설치했다면 이 변수값을 다시 초기화도 시켜줘야 한다. 예를 들어서

  1 1 2 3 이 있다고 생각해보자. 처음 땅의 높이가 1인 두 놈에 의해서 Before_Road의 값은 2가 될 것이고, 경사로를 설치할 것이다.

  만약 초기화를 하지 않았다면, 3을 만났을 때, 그대로 2일 것이고, 경사로를 설치할 수 있다고 판단하는 문제가 생기기 때문이다.

  4번은 계산하고 있는 그 행 혹은 열에서 그대로 계산을 종료시키면 된다. 땅의 높이가 어떻게 되있던 간에, 차이가 2이상인

  한놈만 있어버리면 그 행 혹은 열은 절대로 길이 될 수 없기 때문이다.

2. 위의 내용을 행에 대해서 구현했다면 이제 열에 대해서 구현하면 된다.

  그런데... 여기서.. 기가맥힌 방법을 사용하면 따로 구현하지 않아도 된다.

  본인은 맵을 입력받을 때, 맵을 하나 더 만들었다. 즉, 총 2개의 맵을 가지고 이 문제를 해결했다.

  하나는 입력받는 맵이라고 치면, 다른 하나는?? 행과 열을 바꿔버린 맵이다.

 

 이렇게 !!!!

 이후, 1번에서 말한 4가지 조건을 구현하는 함수 매개변수에 호출을 MAP과 MAP2 이렇게 총 2번을 호출했다.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, L;
int MAP[MAX][MAX];
int MAP2[MAX][MAX];
 
void Input()
{
    cin >> N >> L;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            MAP2[j][i] = MAP[i][j];
        }
    }
}
 
bool Can_Make_Road(int A[][MAX], int x, int y)
{
    int Standard = A[x][y + 1];
    for (int j = y + 1; j < y + 1 + L; j++)
    {
        if (A[x][j] != Standard) return false;
    }
    return true;
}
 
int Make_Road(int A[][MAX])
{
    int Total_Road = 0;
    for (int i = 0; i < N; i++)
    {
        bool Can_Road = true;
        int Before_Road = 1;
 
        for (int j = 0; j < N - 1; j++)
        {
            if (A[i][j] == A[i][j + 1]) Before_Road++;    // 1번 Case
            else if (A[i][j] == A[i][j + 1] + 1)        // 2번 Case 앞에것이 더 높을 때
            {
                if (Can_Make_Road(A, i, j) == true)
                {
                    j = j + L - 1;
                    Before_Road = 0;
                }
                else
                {
                    Can_Road = false;
                    break;
                }
            }
            else if (A[i][j] + 1 == A[i][j + 1])        // 3번 Case 뒤에것이 더 높을 때
            {
                if (Before_Road >= L)
                {
                    Before_Road = 1;
                }
                else
                {
                    Can_Road = false;
                    break;
                }
            }
            else if (abs(A[i][j] - A[i][j + 1]) >= 2)
            {
                Can_Road = false;
                break;
            }
        }
 
        if (Can_Road == true)
        {
            Total_Road++;
        }
    }
    return Total_Road;
}
 
void Solution()
{
    int A = Make_Road(MAP);
    int B = Make_Road(MAP2);
 
    cout << A + B << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}