[C++] 백준 14890번 경사로

14890번: 경사로

삼성 SW 기출문제.

구현 문제이며, 골드3 문제치고는 높은 정답률을 기록하고 있다.

문제에서 세부조건들까지 상세하게 줘서, 문제에 있는 그대로 구현만 하면 맞출 수 있는 문제다.

 

문제풀이

문제의 조건들을 간략하게 요약해보면 다음과 같다.

• N x N 지도에서, 나갈 수 있는 길을 찾는다. 나갈 수 있는 길이란 해당 길에서 높이가 모두 같은 곳을 의미한다.
• 나갈 수 있는 길은, 1행 또는 1열의 모습으로 나타난다. 따라서 최대 2N개가 가능하다.
• 길에는 경사로를 설치할 수 있다. 경사로에 대한 조건은 다음과 같다.

1. 경사로의 높이는 1이고, 길이는 L로 입력을 받는다.
2. 경사로를 설치할 경우, 경사로를 설치할 곳에 모든 높이가 동일해야 한다.
3. 경사로를 설치한 곳에는 또 경사로를 설치할 수 없다.
4. 경사로는 오르막길뿐만 아니라 내리막길에도 설치할 수 있다. 

4번 조건에 의해, 행과 열을 조사할 때, 한쪽 방향으로만 조사해주면 된다.

 

문제에 나와있는 조건과 위 조건들만 잘 고려해주면 풀 수 있다. 이제 코드를 살펴보자.

 

#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;

int widthHeight, floorLength;
int map[101][101];
bool setFloor[101];
int ans;

사용한 변수와 STL이다.

• widthHeight, floorLength : 입력받는 N과 경사로의 길이 L이다.
• map 배열 : 지도의 각 칸의 높이를 저장하는 배열이다.
• setFloor 배열 : 각 행, 또는 열을 조사할때 칸에 경사로가 설치되어있는지 여부를 저장하는 배열이다.
• ans : 출력하는 결과값이다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> widthHeight >> floorLength;

    for (int i = 1; i <= widthHeight; i++) {
        for (int j = 1; j <= widthHeight; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 1; i <= widthHeight; i++) {
        memset(setFloor, false, sizeof(setFloor));
        checkVerticalUpToDown(map[1][i], 2, i);

        memset(setFloor, false, sizeof(setFloor));
        checkHorizontalLeftToRight(map[i][1], i, 2);
    }

    cout << ans;

    return 0;
}

메인함수.

N, L을 입력받고 지도에서 각 칸의 높이를 입력받는다.

그리고 1행, 1열 ~ N행, N열을 조사한다.

1	1	1
1
1

	2
2	2	2
	2

		3
		3
3	3	3

만일 3 x 3 지도가 있다면 위와같은 순서대로 조사하게 될것이다.

checkVerticalUpToDown, checkHorizontalLeftToRight 메서드는 이름에서 보이듯이

위에서 아래, 왼쪽에서 오른쪽으로 가보면서 길이 가능한 곳인지 여부를 체크하는 메서드이다.

하기전에, 이전에 설치한 경사로들을 memset() 메서드를 통해 초기화해준다.

 

추가로, 맨 첫번째 칸은 조사하지 않고 두 번째 칸부터 메서드가 시작된다.

 

void checkVerticalUpToDown(int prevData, int r, int c) {
    if (r > widthHeight) {
        ans++;
        return; 
    }

    if (abs(map[r][c] - prevData) > 1) { return; }
    else {
        if (map[r][c] == prevData) {
            checkVerticalUpToDown(map[r][c], r + 1, c);
        }
        else if (map[r][c] - prevData < 0) {
            
            // 1 더 작은 높이가 나왔다면, 앞으로의 길들에 경사로를 세워준다.
            if (r + floorLength - 1 > widthHeight) { return; } // 범위 벗어난 경우, 경사로 설치 불가.

            //길이 다 같은지, 설치한 곳 있는지 check
            for (int i = r; i < r + floorLength; i++) {
                if (map[i][c] != map[r][c] || setFloor[i]) { return; }
            }

            for (int i = r; i < r + floorLength; i++) {
                setFloor[i] = true;
            }

            int nxtR = r + floorLength;

            checkVerticalUpToDown(map[nxtR - 1][c], nxtR, c);
        }
        else { // 1 더 큰 높이가 나왔다면, 이전까지 길들에 경사로를 세워준다.
            int prevR = r - 1;
            if (prevR - floorLength + 1 < 1) { return; } // 범위 벗어난 경우, 경사로 설치 불가.

            //길이 다 같은지, 설치한 곳 있는지 check
            for (int i = prevR; i > prevR - floorLength; i--) {
                if (map[i][c] != map[prevR][c] || setFloor[i]) { return; }
            }

            for (int i = prevR; i > prevR - floorLength; i--) {
                setFloor[i] = true;
            }

            checkVerticalUpToDown(map[r][c], r + 1, c);
        }
    }
}

void checkHorizontalLeftToRight(int prevData, int r, int c) {

    if (c > widthHeight) {
        ans++;
        return;
    }

    if (abs(map[r][c] - prevData) > 1) { return; }
    else {
        if (map[r][c] == prevData) {
            checkHorizontalLeftToRight(map[r][c], r, c + 1);
        }
        else if (map[r][c] - prevData < 0) {
            // 1 더 작은 높이가 나왔다면, 앞으로의 길들에 경사로를 세워준다.
            if (c + floorLength - 1 > widthHeight) { return; } // 범위 벗어난 경우, 경사로 설치 불가.
            
            //길이 다 같은지, 설치한 곳 있는지 check
            for (int i = c; i < c + floorLength; i++) {
                if (map[r][i] != map[r][c] || setFloor[i]) { return; }
            }

            for (int i = c; i < c + floorLength; i++) {
                setFloor[i] = true;
            }

            int nxtC = c + floorLength;

            checkHorizontalLeftToRight(map[r][nxtC - 1], r, nxtC);
        }
        else { // 1 더 큰 높이가 나왔다면, 경사로를 세워준다.
            int prevC = c - 1;
            if (prevC - floorLength + 1 < 1) { return; } // 범위 벗어난 경우, 경사로 설치 불가.

            //길이 다 같은지, 설치한 곳 있는지 check
            for (int i = prevC; i > prevC - floorLength; i--) {
                if (map[r][i] != map[r][prevC] || setFloor[i]) { return; } //이미 설치한 곳이 있다면 설치불가.
            }

            for (int i = prevC; i > prevC - floorLength; i--) {
                setFloor[i] = true;
            }

            checkHorizontalLeftToRight(map[r][c], r, c + 1);
        }
    }
}

행(수직선), 열(가로선)의 길의 가능성을 조사하는 메서드의 조건은 다음과 같은 구조로 이루어져 있다.

메서드의 매개변수 prevData는 

• 만일 지금 행을 조사하고 있다면 r, 열을 조사하고 있다면 c가 N보다 크다면 이건 길로 가능하다는 뜻이다. ans에 1을 더해주고 return한다.
• 만일 현재 조사중인 칸에서 이전 칸을 뺐을 때의 절대값이 1보다 크다면, 즉 차이가 2 이상이라면 경사로로도 불가능하다. return한다.
• 아니라면, 다음과 조건을 새로 나눈다.

1. 현재 칸이 이전 칸의 높이와 같다면, 그대로 진행시킨다. 행이라면 r + 1, 열이라면 c + 1을 해준다.
2. 현재 칸이 이전 칸의 높이보다 1 작다면 범위가 올바른지 조사하고, 경사로가 설치된 곳은 없는지, 길의 높이가 다 같은지 조사한 후에 경사로를 설치해주고 진행시킨다.
3. 현재 칸이 이전 칸의 높이보다 1 크다면 범위가 올바른지 조사하고, 경사로가 설치된 곳은 없는지, 길의 높이가 다 같은지 조사한 후에 경사로를 설치해주고 진행시킨다.

범위가 올바른지 조사할 때 유의할 점은,

설치할 시작 칸에서 설치할 마지막 칸까지의 차이는 (경사로의 길이 - 1)이란 점이다.

예를 들어서 2부터 4까지 경사로를 설치한다고 하면, 경사로의 길이는 3인데 4 - 2는 2이다.

따라서 범위 조사 조건을 잘 설정해줘야 한다.

 

뭔가 운좋게 한 번에 맞은 것 같다.

문제에 조건이 잘 나와 있어서 좋았던 문제였다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인 가능하다.