백준 14890 / 경사로

문제 설명에 보강이 필요할 것 같다.

처음엔

가로를 체크하고 세로를 체크한다고 할 때,

가로의 경우에서 경사로를 설치한 곳에

세로의 경우 때 경사로를 설치하지 못하는 건 줄 알았다.

즉, 가로의 경우에서 경사로를 설치한 곳은

세로의 경우에서도 경사로를 설치할 수 있다!

(내가 괜히 어렵게 생각한 것일수도...)

문제를  지나갈 수 있는 길의 개수가 아니라, 

길이 될 수 있는 모든 경우의 수를 구하는 것이라 해야할 것 같다.

맵을 100,100 크기로 선언해 놓고 문제에서 주어진 n x n을 넘어가는 곳은 전부 200으로 해놓았다. (포문돌때 넘어가는 경우까지 체크하기 귀찮아서..)

차이가 1일때, 경사로가 지어질 곳의 상태를 미리 파악하고, 설치가 가능하면 설치.

설치는 bool 배열을 사용했다.

가로 세로의 경우를 둘다 해야하기 떄문에, 약간은 노가다(중복코드)로 풀었다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<math.h>
#include<memory.h>
 
using namespace std;
 
int map[101][101];
bool check[101][101];
 
 
int n, l;
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n >> l;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = 200;
            cin >> map[i][j];
        }
 
    }
 
    int ans = 0;
 
    // 가로 체크
    for (int i = 0; i < n; i++) {
        int now = map[i][0];
        bool it = true;
 
        for (int j = 1; j < n; j++) {
            if (map[i][j] == now) {
                continue;
            }
            if (map[i][j] != now) {
                if (abs(now - map[i][j]) > 1) {  // 1 이상 차이가 날때
                    it = false;
                    break;
                }
                else {
                    if (now - map[i][j] == 1) {  // 내려가는 경사를 지어야 할때
                        for (int k = j; k < j + l; k++) {
                            if (map[i][k]!=now-1 || check[i][k]==true) {
                                it = false;
                                break;
                            }
                        }
                        if (it == true) {
                            for (int k = j; k < j + l; k++) {
                                check[i][k] = true;
                            }
                        }
                    }
                    if (now - map[i][j] == -1) { // 올라가는 경사를 지어야 할때
                        if (j < l) {
                            it = false;
                            break;
                        }
                        else {
                            for (int k = j - l; k <= j - 1; k++) {
                                if (map[i][k]!=now ||check[i][k]==true) {
                                    it = false;
                                    break;
                                }
                            }
                            if (it == true) {
                                for (int k = j - l; k <= j - 1; k++) {
                                    check[i][k] = true;
                                }
                            }
                        }
                    }
                    now = map[i][j];
                }
            }
        }
        if (it == true) {
            ans++;
        }
    }
 
    memset(check, false, sizeof(check));
 
 
    //세로 체크
 
    for (int j = 0; j < n; j++) {
        int now = map[0][j];
        bool it = true;
 
        for (int i = 1; i < n; i++) {
            if (map[i][j] == now) {
                continue;
            }
            if (map[i][j] != now) {
                if (abs(now - map[i][j]) > 1) {  // 1 이상 차이가 날때
                    it = false;
                    break;
                }
                else {
                    if (now - map[i][j] == 1) { // 내려가는 경사를 지어야 할때
                        for (int k = i; k < i + l; k++) {
                            if (map[k][j]!=now-1 || check[k][j]==true) {
                                it = false;
                                break;
                            }
                        }
                        if (it == true) {
                            for (int k = i; k < i + l; k++) {
                                check[k][j] = true;
                            }
                        }            
                    }
                    if (now - map[i][j] == -1) { // 올라가는 경사를 지어야 할때
                        if (i < l) {
                            it = false;
                            break;
                        }
                        else {
                            for (int k = i - l; k <= i - 1; k++) {
                                if (map[k][j]!=now || check[k][j]==true) {    
                                    it = false;
                                    break;
                                }
                            }
                            if (it == true) {
                                for (int k = i-l; k <= i -1; k++) {
                                    check[k][j] = true;
                                }
                            }
                        }
                    }
                    now = map[i][j];
                }
            }
        }
        if (it == true) {
            ans++;
        }
    }
 
    cout << ans << endl;
    
}