[백준] 14890번 : 경사로

문제

 

---

풀이

 

어쩌다보니 요즘 삼성 문제에 대한 풀이만 올리는 것 같은데...

구현 문제가 아니고서야 코드가 다 비슷비슷해서 굳이 올리지 않는 것이다.

 

일단 같은 행으로 이루어진 길은 다루기가 쉬운데 같은 열로 이루어진 길은 좀 까다롭다.

그래서 아주 간단한 방법을 썼다.

 

1 2

3 4

이런 지도가 있다고 하자. 이 지도를 값들을

 

1 2

3 4

1 3

2 4

이렇게 저장할 것이다.

그냥 길을 저장할 배열을 지도의 2배로 만들고 같은 열의 길도 같은 행의 길 처럼 저장하는 것이다.

그럼 각각의 길들을 독립적으로 다룰 수 있다.

 

3 2 1 1 2 3

이란 길이 있다고 하자.

맨 왼쪽(i=0)에서부터 맨 오른쪽의 직전 위치(i=4)까지 살펴볼 것인데

 

i=0 일 때를 보자.

3->2로 내리막 경사로를 설차해야 한다. 경사로를 앞으로 설치하는 것이다.

 

i=3 일 때를 보자.

1->2로 오르막 경사로를 설치해야 한다. 경사로를 뒤로 설치하는 것이다.

 

이 차이는 꽤 중요하고, 뭔 말인지 이해가 안된다면 코드를 같이 보면 된다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

bool isPromise(vector<int> v, int size, int L) {
    vector<bool> installed(size, false); //경사로 설치 여부 확인
    for (int i = 0; i < size - 1; i++) {
        if (abs(v[i] - v[i + 1]) > 1) //높이 차이 2이상 -> 경사로 설치 불가
            return false;
        if (v[i] < v[i + 1]) { //오르막길 설치
            for (int j = i; j > i - L; j--) { //경사로 설치
                if ((v[j] != v[i]) || (j < 0) || installed[j]) //평평한 길이 충분하지 않거나 경사로가 이미 설치 됐다면
                    return false;
            }
        } else if (v[i] > v[i + 1]) { //내리막길 설치
            for (int j = i + 1; j <= i + L; j++) { //경사로 설치
                if ((v[j] != v[i + 1]) || (j == size)) //평평한 길이 충분하지 않으면
                    return false;
                installed[j] = true;
            }
        }
    }
    return true; //갈 수 있는 길
}

int main() {
    int N, L;

    cin >> N >> L;
    vector<vector<int>> roads(2 * N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roads[i][j]; //가로 길
            roads[j + N][i] = roads[i][j]; //세로 길
        }
    }
    int result = 0;
    for (int i = 0; i < 2 * N; i++) {
        if (isPromise(roads[i], N, L)) //지나갈 수 있는 길인지 확인
            result++;
    }
    cout << result;
}

전체 소스코드다.

 

int main() {
    int N, L;

    cin >> N >> L;
    vector<vector<int>> roads(2 * N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> roads[i][j]; //가로 길
            roads[j + N][i] = roads[i][j]; //세로 길
        }
    }
    int result = 0;
    for (int i = 0; i < 2 * N; i++) {
        if (isPromise(roads[i], N, L)) //지나갈 수 있는 길인지 확인
            result++;
    }
    cout << result;
}

메인은 아주 간단하다. 먼저 모든 길을 roads라는 2차원 벡터에 저장할 것이다.

그리고 모든 길에 대해서 isPromise로 지나갈 수 있는 길인지 확인하고 그렇다면 result를 증가한다.

마지막으로 result를 출력하면 된다.

 

그럼 isPromise 함수를 보도록 하겠다.

 

bool isPromise(vector<int> v, int size, int L) {
    vector<bool> installed(size, false); //경사로 설치 여부 확인
    for (int i = 0; i < size - 1; i++) {
        if (abs(v[i] - v[i + 1]) > 1) //높이 차이 2이상 -> 경사로 설치 불가
            return false;
        if (v[i] < v[i + 1]) { //오르막길 설치
            for (int j = i; j > i - L; j--) { //경사로 설치
                if ((v[j] != v[i]) || (j < 0) || installed[j]) //평평한 길이 충분하지 않거나 경사로가 이미 설치 됐다면
                    return false;
            }
        } else if (v[i] > v[i + 1]) { //내리막길 설치
            for (int j = i + 1; j <= i + L; j++) { //경사로 설치
                if ((v[j] != v[i + 1]) || (j == size)) //평평한 길이 충분하지 않으면
                    return false;
                installed[j] = true;
            }
        }
    }
    return true; //갈 수 있는 길
}

installed 벡터는 특정 위치에 대한 경사로 설치 여부를 저장한다.

먼저 v[i]와 v[i+1]의 높이 차이가 1보다 크다면 바로 false를 리턴한다.

 

그 다음으론 오르막길을 설치해야 하는지 확인한다.

앞서 말했듯이 오르막 경사로는 자기자신을 포함하여 L만큼 뒤에 설치해야 한다.

그러므로 경사로를 설치할 L만큼의 평평한 길이 충분히 있는지 확인하고, 혹시 그곳에 이미 경사로를 설치하지 않았는지도 확인한다. 굳이 오르막 경사로를 설치했다고 installed를 표시할 필요는 없다.

왼쪽->오른쪽으로 탐색하기 때문에 탐색하게 될 일이 없기 때문이다.

 

또는 내리막길을 설치해야 하는지 확인한다.

내리막 경사로는 자기자신의 다음부터 L만큼 앞에 설치해야 한다.

그러므로 경사로를 설치할 L만큼의 평평한 길이 충분히 있는지만 확인한다. installed 여부를 확인할 필요는 없다. 당연히 설치가 안됐을 것이기 때문이다.

그리고 이번엔 내리막 경사로를 설치했다는 표시를 한다.

 

이렇게 길의 끝까지 이동하는데 성공했다면 true를 반환한다.