백준 14890 경사로 c++ [컴공과고씨]

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

14890번: 경사로

 

문제 간단 정리

한 행렬이 있을 때 한 행으로 쭉 갈거나 한 열로 쭉 갈 수 있다면 그것은 길이다.

길의 개수를 세야함.

근데 각 좌표에는 높이가 있음.

높이가 다르면 경사로를 설치해서 지나갈 수 있음.

경사로 설치 조건

1. 높이 차는 1이여야함.

2. L이 주어지는데 높이가 낮은 쪽에 L개수 만큼 같은 높이로 좌표가 있어야 설치가 가능함.

3. 경사로는 곂쳐지면 안됨.

 

 

문제 해결 방법

일단 행렬이 있을 때 가로 길을 확인 하는 함수를 구현했습니다.

한 행을 정하고 그 행 1열 부터 N까지 하나씩 나아갑니다.

이 때 다음 좌표를 높이를 보고 3가지 경우로 일단 나누어 줍니다.

1. 다음 좌표가 높이 차가 1보다 더 크게 날 때 => 이미 길이 될 수 없으므로 이 행은 X

2. 다음 좌표가 1만큼 작아 지나갈 길에 경사로를 설치 할 때

   2-1) 지나갈 좌표 중 L만큼의 같은 높이로 이루어져 있는지

     2-2) 위 조건을 만족하지 않으면 경사로 설치 불가능.

     2-3) 만족하면 경사로가 설치된 마지막 좌표에 경사로가 설치되었다고 표시 -> 경사로 곂치는 것을 막기 위해.

3. 다음 좌표가 1만큼 커서 지나온 길에 경사로를 설치 할 때

   3-1) 지나온 좌표를 확인하며 L만큼 같은 높이로 이루어져 있는지 확인

   3-1) 이 부분에서는 지나온 길에 경사로가 설치되어있는지 꼭 확인해주어야 함.

      3-2)  불가능 하면 경사로 설치 불가능.

 

1,2,3을 모두 통과하면 길로 인정함.

 

 

이렇게 가로를 확인하는 행렬을 만들었다면 그 세로 길을 확인하는 방법은 세로로 된 길을 가로길로 만들어서 함수에 넘겨주면 된다.

무슨 말이냐면 문제에서 준 행렬의 X좌표와 Y좌표를 바꾸어주면 세로였던 길이 가로로 가게 되고 가로였던길이 세로로 간다.

그래서 바꾸어준 행렬을 다시 함수에 넣어주어 길의 개수를 세주면 된다.

 

전체 코드

#include <iostream>
#include <cmath>
using namespace std;
int road1[101][101];
int road2[101][101];
int n, l;
int result = 0;
void PassCnt(int road[][101]){
    //가로 확인
    for (int i = 0; i < n; i++){  
        bool slope[101] = {0}; // 경사로 여부
        bool possible = true; // 가능한 길인지 확인
        for (int h = 0; h < n-1; h++){
            if(abs(road[i][h]-road[i][h+1]) > 1){
                // 1. 높이차가 1보다 크면 불가능한 길 
                possible = false;
                break;
            }
            
            // 2. 경사로를 위에서 아래로 설치 할 때
            if(road[i][h] == road[i][h+1] + 1){
                int cur_hight = road[i][h + 1];
                for (int k = h+2; k < h+1+l; k++){
                    if(k >= n || road[i][k] != cur_hight){
                        //L만큼의 여유가 있는지 확인
                        possible = false;
                        break;
                    }
                }
                if(possible){
                    //경사로 설치하면 설치했다고 표시
                    slope[h + l] = true;
                }else{
                    break;
                }
            }
 
            // 3. 경사로를 아래에서 위로 설치 할 때
            if(road[i][h] == road[i][h+1] - 1){
                int cur_hight = road[i][h];
                for (int k = h; k > h - l; k--){
                    if(k < 0 || road[i][k] != cur_hight || slope[k]){
                        // L만큼의 여유와 경사로 설치 여부 확인
                        possible = false;
                        break;
                    }
                }
                if(!possible){
                    break;
                }
            }
        }        
        if(possible){
            result++; // 길이면 카운트
        }
    }
}
 
int main(){
    cin >> n >> l; // 입력
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> road1[i][j]; // 가로로 가는 길 확인
            road2[j][i] = road1[i][j]; // 세로로 가는 길 확인
        }
    }
    PassCnt(road1); // 가로로 가는 길 개수
    PassCnt(road2); // 세로로 가는 길 개수
    cout << result << endl;
 
    return 0;
}

체감 난이도	걸린 시간
중	40M

 

문제가 복잡해 보여도 하나씩 따라가면 풀 수 있는 문제였습니다.