[백준/C++] 14890 - 경사로

풀이 시간: 2h12m17s71

시간 복잡도: O(N^2*L)

공간 복잡도: O(N^2)

문제

입력

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

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

문제 풀이

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, L, ans = 0;
vector<bool> cnt1, cnt2;
int arr1[101][101] = { 0, };
int arr2[101][101] = { 0, };

vector<bool> isRoad(int arr[][101]) {
    vector<bool> cnt(N, true); // 각각의 길을 지나갈 수 있는지 여부
    bool ramp[101][101] = { false, }; // 경사로 설치
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            if (arr[i][j] == arr[i][j + 1]) continue; // 같은 높이일 경우 continue
            else if (abs(arr[i][j] - arr[i][j + 1]) == 1) { // 크기 1 차이
                if (arr[i][j] > arr[i][j + 1]) { // 현재 값이 더 큰 경우
                    ramp[i][j + 1] = true; // 다음 위치 true
                    for (int k = j + 1; k < j + 1 + L; ++k) { // 다음 위치부터 L만큼 다음 값 탐색
                        if (k >= N || arr[i][j + 1] != arr[i][k]) // 경사로 못놓는 경우 false
                            { cnt[i] = false; break; }
                        else ramp[i][k] = true; // 경사로 놓기
                    }
                }
                else { // 현재 값이 더 작은 경우
                    for (int k = j; k > j - L; --k) { // 현재 값부터 L만큼 이전 값 탐색
                        if (k < 0 || arr[i][j] != arr[i][k]) // 경사로 못놓는 경우 false
                            { cnt[i] = false; break; }
                        else { // 경사로를 놓을 수 있는 경우
                            if (!ramp[i][k]) ramp[i][k] = true; // 경사로 놓기
                            else { cnt[i] = false; break; } // 이미 경사로가 있는 경우 false
                        }
                    }
                }
            }
            else { cnt[i] = false; break; } // 값의 차이가 2일 경우 false 후 해당 길 종료
        }
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> L;
    cnt1 = cnt2 = vector<bool>(N, true);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            cin >> arr1[i][j];
            arr2[j][i] = arr1[i][j];
        }
    cnt1 = isRoad(arr1);
    cnt2 = isRoad(arr2);
    for (int i = 0; i < N; ++i) { // 지나갈 수 있는 길 카운트
        if (cnt1[i]) ans++;
        if (cnt2[i]) ans++;
    }
    cout << ans;
    return 0;
}

 

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

14890번: 경사로