카테고리 없음

[백준] 14890_경사로

arock 2024. 12. 27. 17:45
반응형

1. 문제

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

 

 

각 행 또는 열의 한 쪽 끝에서 반대쪽 끝까지 이동할 수 있는 길의 수를 구하라. 숫자는 길의 높이로 볼 수 있고, 높이가 다른 길은 경사로를 통해서 이동할 수 있다. 경사로를 놓을 수 있는 조건은 아래와 같다. (단, 경사로는 다른 길에 영향을 끼치지 않는다.)

  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
  • 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

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

  • 경사로를 놓은 곳에 또 경사로를 놓는 경우
  • 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
  • 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
  • 경사로를 놓다가 범위를 벗어나는 경우

2. 문제 풀이

하나의 길을 하나의 배열 v로 보았을 때, 반복문을 돌면서 현재 인덱스 i 번째까지 올 수 있는지 아닌지를 판단한다. i 번째 인덱스에서 판단할 수 있는 경우의 수는 다음과 같다.

  1. 앞과 높이가 같은 경우 → 계속 진행 v[i-1] = v[i]
  2. 앞과 높이가 2이상 차이나는 경우 → 길 통행 X
  3. 경사로를 i 이전에 두어야 하는 경우 v[i-1] - v[i] = -1
  4. 경사로를 i 부터 두어야 하는 경우 v[i-1] - v[i] = 1

길에 경사로를 중복해서 둘 수 없으므로 배열 r을 사용해 경사로 두었는지 여부를 체크한다.

3. 코드

길 하나씩을 배열로 담고 checkCross 함수를 사용하여 길을 지날 수 있는지 확인합니다.

#include <bits/stdc++.h>
using namespace std;

int m[101][101];
int r[101];
int N, L;

int checkCross(vector<int> v){
    fill_n(r, N, 0);

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

        // 1. 앞과 높이가 같은 경우 → 계속 진행
        if(v[i-1] == v[i]) continue;

        // 2. 앞과 높이가 2이상 차이나는 경우 → 길 통행 X
        if(abs(v[i-1]-v[i])>=2) return 0;

        // 3. 경사로를 i 이전에 두어야 하는 경우 
        if(v[i-1] - v[i] == -1) {
            if(i-L < 0) return 0;
            for(int j = i-L; j < i; j++) {
                if(v[j] != v[i-1]) return 0;
                if(r[j]) return 0;
                r[j] = 1;
            }
        }
        
        // 4. 경사로를 i 부터 두어야 하는 경우
        if(v[i-1] - v[i] == 1) {
            if(i+L > N) return 0;
            for(int j = i; j < i+L; j++) {
                if(v[j] != v[i]) return 0;
                r[j] = 1;
            }
            i = i+L-1;
        }
    }
    return 1;
}

int main() {
    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 >> m[i][j];
        }
    }

    int res = 0;

    // 가로 행으르 돌면서 확인하기
    for(int i = 0; i < N; i++) {
        vector<int> v(begin(m[i]), begin(m[i]) + N);
        if(checkCross(v) == 1) res++;

    }

    // 세로 행으로 돌면서 확인하기
    for(int i = 0; i < N; i++) {
        vector<int> v;
        for(int j = 0; j < N; j++) {
            v.push_back(m[j][i]);
        }
        if(checkCross(v) == 1) res++;
    }

    cout << res << "\\n";

}
반응형