백준 14890: 경사로(c++, 구현)

사용 언어	티어	시간 제한	메모리 제한
c+=		2초	512MB

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

14890번: 경사로

 

#0 문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 
오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 
다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.
경사로를 놓은 곳에 또 경사로를 놓는 경우낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우경사로를 놓다가 범위를 벗어나는 경우
L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.
가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

 

#1 입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

 

#2 접근

• 삼성 코테 기출문제이다. 구현에 해당하며 꼼꼼하게 프로그램을 작성하면 된다.
• 높이 차이가 1일 때만 경사로를 놓을 수 있다는 것에 주의하자.
• 경사로는 겹치면 안되고, 경사로를 놓을 때에는 칸의 높이가 다 같아야 한다. 기준 L에 맞도록 구현해야한다.
• 여러 케이스들을 잘 고려해서 실수 없이 구현하는 것이 중요하다.

 

#3 풀이

• 우선 지도에 해당하는 배열과, 경사로 중복 체크를 위한 배열을 만들어둔다.
• 이후 각 행을 체크하고, 각 열을 체크하면 된다.
• 높이 차이가 0일 때는 문제가 없으므로 그냥 넘어간다.
• 높이 차이가 1일 때
  • 오르막과 내리막 두 가지 경우가 있다.
  • 내리막의 경우
    • 현재 칸이 바로 이전 칸보다 높이가 1 작다.
    • L이 1보다 클 경우
      • 현재 칸이 마지막 index일 경우 범위를 벗어나므로 경사로를 놓을 수 없다.
      • 연속하는 같은 높이의 칸이 L만큼은 있어야하므로 연속하는 칸의 수를 센다.
      • 연속하는 칸의 수가 L보다 작을 경우는 경사로를 놓을 수 없다.
      • 연속하는 칸의 수가 L이상일 경우에는 L칸에 경사로를 놓는다.
    • L이 1일 경우
      • 바로 경사로를 놓으면 된다.
  • 오르막의 경우
    • 현재 칸이 바로 이전 칸보다 높이가 1 높다.
    • L이 1보다 클 경우
      • 현재 칸이 1번 index라면 범위를 벗어나므로 경사로를 놓을 수 없다.
      • 연속하는 같은 높이의 칸이 L만큼은 있어야하므로 연속하는 칸의 수를 센다.
      • 연속하는 칸의 수가 L보다 작을 경우는 경사로를 놓을 수 없다.
      • 연속하는 칸의 수가 L이상일 경우에는 L칸에 경사로를 놓는다.
        • 이 경우 이전의 내리막 경사로랑 겹칠 확률이 존재하므로, 내리막 경사로가 있었을 경우에는 경사로를 놓지 않는다.
    • L이 1인 경우
      • 바로 경사로를 놓으면 된다.
• 높이 차이가 1보다 클 경우
  • 경사로를 놓지 못한다.
• 위와 같은 방식으로 행에 대해 먼저 진행해주고, 경사로 정보를 초기화한 후 열에 대해 진행해주면 된다.

 

#4 코드

/*
14890 경사로
구현
*/

#include <iostream>
#include <cstring>

using namespace std;


int n, l;

int board[101][101];
int slope[101][101];
int ans;


void solve() {
    // 어쨌든 갈라면 무조건 경사로 놓기는 해야함
    // 경사로의 유무를 기록해둘 필요가 있음
    // 경사로의 길이도 중요함 -> 경사로의 길이가 2일 때는 같은 수가 연속으로 2번 이상 존재해야함

    // 행 체크하기
    for (int i = 0; i < n; ++i) {
        // 각 행에 관하여

        int prev = board[i][0];
        int check = true;
        for (int j = 1; j < n; ++j) {
            int diff = board[i][j] - prev;

            // 높이 차이가 0이면 상관 없음
            if (diff == 0) {
                continue;
            } else if (diff == -1) {
                // 높이 차이가 1일 경우에는 경사로를 놓을 수 있다.
                // 내리막에 해당
                if (l > 1) {
                    int cnt = 1;
                    int value = board[i][j];
                    if (j == n - 1) {
                        // 이 경우는 마지막이기 때문에 불가능함 -> false return;
                        check = false;
                        break;
                    }
                    // L이 2 이상인 경우 -> 길이 L만큼 cnt가 되어야 경사로를 놓을 수 있음
                    for (int k = j + 1; k < n; ++k) {
                        if (board[i][k] == value) {
                            cnt++;
                        } else {
                            break;
                        }
                    }

                    // cnt가 l 이상일 경우에는 경사로를 놓을 수 있다. L 만큼 경사로 놓아주면 된다.
                    if (cnt >= l) {
                        for (int k = j; k < j + l; ++k) {
                            slope[i][k] = 1;
                        }
                    } else {
                        // 이 경우 경사로의 길이만큼 블럭의 수가 존재하지 않으므로 불가능함 
                        check = false;
                        break;
                    }
                } else {
                    // L이 1인 경우 -> 경사로 그냥 바로 놓으면 됨
                    slope[i][j] = 1;
                }
            } else if (diff == 1) {
                // 오르막에 해당
                if (l > 1) {
                    int cnt = 1;
                    int value = prev;
                    if (j == 1) {
                        // j가 1인 경우엔 앞에 길이 L짜리 경사로를 놓을 수 없다
                        check = false;
                        break;
                    }
                    // L이 2 이상인 경우 -> 길이 L만큼 cnt가 되어야 경사로를 놓을 수 있음
                    for (int k = j - 2; k >= 0; --k) {
                        if (board[i][k] == value) {
                            cnt++;
                        } else {
                            break;
                        }
                    }

                    // cnt가 l 이상일 경우에는 경사로를 놓을 수 있다. L 만큼 경사로 놓아주면 된다.
                    if (cnt >= l) {
                        for (int k = j - 1; k >= j - l; --k) {
                            if (slope[i][k]) {
                                check = false;
                                break;
                            } else slope[i][k] = 1;
                        }
                    } else {
                        // 이 경우 경사로의 길이만큼 블럭의 수가 존재하지 않으므로 불가능함 
                        check = false;
                        break;
                    }
                } else {
                    // L이 1인 경우 -> 경사로 그냥 바로 놓으면 됨 -> 이미 경사로가 존재할 경우는 제외하고
                    if (slope[i][j - 1]) {
                        check = false;
                        break;
                    } else slope[i][j - 1] = 1;
                }
            } else {
                check = false;
                break;
            }
            prev = board[i][j];
        }
        if (check) {
            ans++;
        }
    }

    memset(slope, 0, sizeof(slope));

    // 열 체크하기
    for (int i = 0; i < n; ++i) {
    // 각 열에 관하여
        int prev = board[0][i];
        int check = true;
        for (int j = 1; j < n; ++j) {
            int diff = board[j][i] - prev;

            // 높이 차이가 0이면 상관 없음
            if (diff == 0) {
                continue;
            } else if (diff == -1) {
                // 높이 차이가 1일 경우에는 경사로를 놓을 수 있다.
                // 내리막에 해당
                if (l > 1) {
                    int cnt = 1;
                    int value = board[j][i];
                    if (j == n - 1) {
                        // 이 경우는 마지막이기 때문에 불가능함 -> false return;
                        
                        check = false;
                        break;
                    }
                    // L이 2 이상인 경우 -> 길이 L만큼 cnt가 되어야 경사로를 놓을 수 있음
                    for (int k = j + 1; k < n; ++k) {
                        if (board[k][i] == value) {
                            cnt++;
                        } else {
                            break;
                        }
                    }
                    // cnt가 l 이상일 경우에는 경사로를 놓을 수 있다. L 만큼 경사로 놓아주면 된다.
                    if (cnt >= l) {
                        for (int k = j; k < j + l; ++k) {
                            slope[k][i] = 1;
                        }
                    } else {
                        // 이 경우 경사로의 길이만큼 블럭의 수가 존재하지 않으므로 불가능함 
                        check = false;
                        break;
                    }
                } else {
                    // L이 1인 경우 -> 경사로 그냥 바로 놓으면 됨
                    slope[j][i] = 1;
                }
            } else if (diff == 1) {
                // 오르막에 해당
                if (l > 1) {
                    int cnt = 1;
                    int value = prev;
                    if (j == 1) {
                        // j가 1인 경우엔 앞에 길이 L짜리 경사로를 놓을 수 없다
                        check = false;
                        break;
                    }
                    // L이 2 이상인 경우 -> 길이 L만큼 cnt가 되어야 경사로를 놓을 수 있음
                    for (int k = j - 2; k >= 0; --k) {
                        if (board[k][i] == value) {
                            cnt++;
                        } else {
                            break;
                        }
                    }

                    // cnt가 l 이상일 경우에는 경사로를 놓을 수 있다. L 만큼 경사로 놓아주면 된다.
                    if (cnt >= l) {
                        for (int k = j - 1; k >= j - l; --k) {
                            if (slope[k][i]) {
                                check = false;
                                break;
                            } else slope[k][i] = 1;
                        }
                    } else {
                        // 이 경우 경사로의 길이만큼 블럭의 수가 존재하지 않으므로 불가능함 
                        check = false;
                        break;
                    }
                } else {
                    // L이 1인 경우 -> 경사로 그냥 바로 놓으면 됨 -> 이미 경사로가 존재할 경우는 제외하고
                    if (slope[j - 1][i]) {
                        check = false;
                        break;
                    } else slope[j - 1][i] = 1;
                }
            } else {
                check = false;
                break;
            }
            prev = board[j][i];
        }

        if (check) {
            ans++;
        }
    }
}


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


    cin >> n >> l;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> board[i][j];
        }
    }

    solve();

    cout << ans;




    return 0;
}