[Beakjoon] 14890 경사로 (C++)

문제 링크

BOJ 14890 : 경사로

문제

시뮬레이션 문제는 문제 쓰기가 귀찮다..

N*N 배열이 주어진다.
'길'로 정의 되는 것은 한 행이나 한 열의 전부이다.
지나갈 수 있는 길을 찾는 문제이다.

지나가기 위한 조건

1. 높이가 같다.
2. 높이가 다른 경우 경사로를 설치할 수 있어야 한다.

경사로를 설치하기 위한 조건

1. 높이 차이가 1이어야 한다.
2. 경사로를 설치하기 위한 여유 공간 L이 있어야 한다.
   

그림이 주어져서 문제를 이해하기가 수월했다.

풀이

먼저 N*N배열에서 '길'을 추출한다.
getRoads()메서드로 구현해서 행과 열을 하나의 2차원 벡터에 저장했다.

길을 확인하면서 지나갈 수 있는지 없는지 판별하는 메서드인 can_go()를 구현했다.

현재 위치를 now로 정의하고 앞의 칸이 더 높은 경우와 낮은 경우를 분리해서 생각했다.

경사로가 이미 설치된 자리일 가능서을 배제하기 위해 check[]배열에 특정 위치에 경사로가 설치됐는지를 체크했다.

경사로 설치가 필요한 시점에

• 위로 올라가는 경사로를 설치하는 경우
  진행 방향 뒷쪽으로 여유공간이 L만큼 있는지 확인한다.
  여기서 여유공간이란 경사로가 설치되지 않았고, 경사로 설치 시작 지점과 높이가 같은 것이 조건이다.

• 아래로 내려가는 경사로를 설치하는 경우
  현재 위치 앞쪽부터 여유공간이 L만큼 있는지 확인한다.

코드

#include<bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

int N,L;
int A[101][101];
vector<vector<int>> V;

void getRoads(){
    for(int i=0; i<N; i++){
        vector<int> c;
        vector<int> r;
        for(int j=0; j<N; j++){
            r.push_back(A[i][j]);
            c.push_back(A[j][i]);
        }
        V.push_back(c);
        V.push_back(r);
    }
}

bool can_go(vector<int> v){
    int now = 0;
    int check[N]; for(int i=0; i<N; i++) check[i] = 0;
    while(now<N-1){
        if(v[now] == v[now+1]) now++;
        else if(v[now]<v[now+1]){
            if(abs(v[now]-v[now+1])>1) return false;
            int tmp = now;
            while(tmp>=0 && v[tmp]==v[now]&&check[tmp]==0&&now-tmp<L){
                check[tmp] =1; tmp--;
            }
            if(now-tmp!=L) return false;
            else now++;
        }
        else {
            if(abs(v[now]-v[now+1])>1) return false;
            now++;
            int tmp = now;
            while(tmp<N && v[tmp]==v[now]&&check[tmp]==0&&tmp-now<L){
                check[tmp] =1; tmp++;
            }
            if(tmp-now!=L) return false;
        }
    }
    return true;
}

void Solve() {
    cin>>N>>L;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>A[i][j];
        }   
    }

    getRoads();
    int answer=0;
    for(int i=0; i<V.size(); i++){
        if(can_go(V[i])) answer++;
    }


    cout<<answer;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}

최근 구현 문제를 풀기 시작했는데, 여태까지 푼 문제 중 비교적 쉽게 풀었다.
나름 꼼꼼하게 생각하는 법을 알아가는 건지 운이 좋았던 건지 모르겠다.