[백준 14890번] 경사로

문제 링크: https://www.acmicpc.net/problem/14890

14890번: 경사로

<문제 풀이> 구현
각 행의 0열부터 N-1까지 순회하면서 다음 두 가지를 경우를 체크해주면 됩니다.

1. 낮은 칸에서 높은칸으로 변화한 경우
    a. 높이 차가 1이 아닌 경우 경사로를 놓을 수 없으므로 지나갈 수 없다.
    b. 왼쪽 방향으로 길이가 L인 경사로를 놓는다.
        -> 높이가 변화한 지점에서부터 왼쪽으로 한 칸씩 이동해보면서 경사로를 놓아본다(높이가 같아야 함)
        -> 이때 방문 체크 배열을 사용해서 이전에 경사로를 놓았는지 여부도 함께 체크
        -> 경사로를 놓을 수 있는 위치이면 cnt을 1씩 증가
        -> 왼쪽으로 순회를 끝냈을 때 cnt와 L을 비교해서 같으면 경사로를 놓을 수 있고, 다르면 지나갈 수 없는 길
2. 높은 칸에서 낮은 칸으로 변화한 경우
        -> 1번이랑 같은 알고리즘

위의 알고리즘으로 함수를 구현해서 0 to N-1 행을 인자로 전달하면 됩니다.

 for (int i = 0; i < N; i++) {

        if (passalbe(i)) res++;

    }


이제 열에 대해서도 위와 똑같은 함수를 구현해도 되지만,
아래 처럼 배열을 90도로 회전시키는 함수를 구현해서, 배열을 회전하고 위 함수를 호출하면,
열에 대해서 알고리즘을 적용한 것과 동일합니다.


/*배열 90도 회전*/

void rotate() {

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            temp[i][j] = board[i][j];

        }

    }

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            board[j][N - i - 1] = temp[i][j];

        }

    }

}

/*열을 기준으로*/
rotate();

fill(&visited[0][0], &visited[99][100], 0);

for (int i = 0; i < N; i++) {

if (passalbe(i)) res++;

}

<C++ 소스 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N, L;
int board[100][100];
bool visited[100][100];
int temp[100][100];
/*배열 90도 회전*/
void rotate() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[j][N - i - 1] = temp[i][j];
        }
    }
}
 
bool passalbe(int r) {
    int cur = board[r][0];
    for (int nc = 1; nc < N; nc++) {
        if (board[r][nc] > cur) { // 낮은 칸에서 높은 칸
            if (board[r][nc] - cur != 1) return false; // 높이 차가 1이 아니면
            int cnt = 0;
            cur = board[r][nc - 1];
            for (int j = nc - 1; j >= 0; j--) { //왼쪽으로 경사로를 놓아본다
                if (board[r][j] == cur && !visited[r][j]) {//높이는 모두 같아야하고 경사로를 중복해서 놓지 못한다
                    visited[r][j] = true;
                    cnt++;
                }
                else break;
                if (cnt == L) break;
            }
            if (cnt != L) return false; //경사로를 놓을 수 없으면
        }
        else if (board[r][nc] < cur) { // 높은 칸에서 낮은곳
            if (cur - board[r][nc] != 1) return false; // 높이 차가 1이 아니면
            int cnt = 0;
            cur = board[r][nc];
            for (int j = nc; j < N; j++) { //오른쪽으로 경사로를 놓아본다
                if (board[r][j] == cur && !visited[r][j]) { //높이는 모두 같아야하고 경사로를 중복해서 놓지 못한다
                    visited[r][j] = true;
                    cnt++;
                }
                else break;
                if (cnt == L) break;
            }
            if (cnt != L) return false; //경사로를 놓을 수 없으면
        }
        
        cur = board[r][nc];
    }
    return true;
}
 
int main(void) {
    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (passalbe(i)) res++;
    }
    rotate();
    fill(&visited[0][0], &visited[99][100], 0);
    for (int i = 0; i < N; i++) {
        if (passalbe(i)) res++;
    }
    cout << res;
    return 0;
}