14890번-경사로

문제

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

14890번: 경사로

---

접근방법

1) 접근 사고

정말 구현문제 그 자체였습니다. 특별한 알고리즘 없이 구현력만 보는 문제인데 문제 설명이 저는 한 번에 이해가가지 않아서 어려웠습니다.

자세한 동작은 주석 첨부 하였습니다.

 

2) 시간 복잡도

O(n^2)

 

3) 배운 점

breack과 continue 사용 연습을 엄청 한 문제였습니다.

 

4) PS

문제 이해가 너무 어려웠다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 100;
int n, l;
int board[MAX][MAX];
bool visited[MAX];
int ret;
 
 
int main(void)
{
    fastio;
    cin >> n >> l;
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
        }
    }
 
    auto checkRow = [&](int y) -> void{
        int cur = board[y][0];
        for(int i = 0; i < n; i++){
            //값이 다른 경우라면
            if(board[y][i] != cur){
                //경사로의 높이가 1이 아니라면
                if(!(abs(board[y][i] - cur) <= 1))
                    return ;
                //내리막길일 경우
                if(board[y][i] < cur){
                    int height = -1;
                    //아직 방문하지 않은 곳이고 내리막길을 만들려는 범위가 n을 초과하지 않는다면
                    for(int j = i; j < i + l; j++){
                        if(!visited[j] && j < n){
                            visited[j] = true;
                            //L길이만큼 같은 높이기가 아니라면 조건 충족 X
                            if (height == -1){
                                height = board[y][j];
                                continue;
                            }
                            if(height != -1 && board[y][j] != height)
                                return;
                        }
                        else
                            return;
                    }
                    //내리막길을 설치한 경로만큼 탐색 인덱스 증가
                    i += l - 1;
                    //초과할 경우 탐색 종료
                    if(i >= n)
                        break;
                }
                else{
                    int height = -1;
                    for (int j = i - 1; j > i - 1 - l; j--){
                        if(!visited[j] && j >= 0)
                        {
                            visited[j] = true;
                            if(height == - 1)
                            {
                                height = board[y][j];
                                continue;
                            }
                            if (height != -1 && board[y][j] != height)
                                return;
                        }
                        else
                            return;
                    }
                }
                cur = board[y][i];
            }
        }
        ret++;
    };
 
    auto checkCol = [&](int x) -> void {
        int cur = board[0][x];
        for(int i = 0; i < n; i++){
            if(board[i][x] != cur){
                if(!(abs(board[i][x] - cur) <= 1))
                    return;
                if(board[i][x] < cur){
                    int height = -1;
                    for(int j = i; j < i + l; j++){
                        if(!visited[j] && j < n){
                            visited[j] = true;
                            if(height == - 1){
                                height = board[j][x];
                                continue;
                            }
                            if(height != -1 && board[j][x] != height){
                                return;
                            }
                        }
                        else
                            return;
                    }
                    i += l - 1;
                    if(i >= n)
                        break;
                }
                else{
                    int height = -1;
                    for(int j = i - 1; j > i - 1 - l; j--){
                        if(!visited[j] && j >= 0){
                            visited[j] = true;
                            if(height == -1){
                                height = board[j][x];
                                continue;
                            }
                            if(height != - 1 && board[j][x] != height)
                                return;
                        }
                        else
                            return;
                    }
                }
                cur = board[i][x];
            }
        }
        ret++;
    };
 
    for(int i = 0; i < n; i++){
        memset(visited, false, sizeof visited);
        checkRow(i);
    }
    for(int i = 0; i < n; i++){
        memset(visited, false, sizeof visited);
        checkCol(i);
    }
    cout << ret << "\n";
}