백준 14890 경사로

일단 문제가 길어서 좀 잘렸다..

 

처음 봤을 때 좀 복잡하겠다 싶었는데, 문제 자체가 어렵다기 보다는 index를 가지고 노는 것이 힘들었던 문제였다.

문제를 읽고 이해가 안되었던 부분도 있었고.. 그래서 힘들었던 것 같다.

결국 index 때문에 정신이 혼란해서 강의를 보고 풀게 되었다..

 

1. 먼저 잘못한 것은 경사로를 놓을 수 있는지 check할 때, i와 i+1 두 인덱스를 가지고 검사하려다 보니, 한 칸씩 검사를 하면 되는 것을 두 칸씩 검사하여 코드도 복잡해지고 내 머리속도 복잡해졌다..

어떤 인덱스를 기준으로 왼쪽으로 더 가거나 오른쪽으로 더 갈 때 i-j, i+j와 같이 푸는 방법을 잘 기억해둬야겠다.

 

2. 길을 찾기 위해서는 행이든 열이든 한 줄씩만 검사하면 된다. 처음에 그렇게 풀려고 했으나, 어떻게 해야 될지 잘 떠오르지 않았고, 시간이 지나다 보니 그냥 2차원 배열 자체로 검사하게 되었다. 당연히 코드가 복잡해졌다.

강의를 듣고 보니, vector를 선언하여, 그 안에 한 줄씩 넣고, 이를 인자로 전달하면 되었다.

이러한 풀이법도 머리에 잘 넣어둬야 겠다..

 

3. 주의할 점이 있었다. 이미 경사로가 있거나, 높이가 안맞거나, 범위를 벗어나는 경우 길이 될 수 없다는 조건이 존재한다. 이 때 범위를 벗어나는 경우를 먼저 처리해 주어야 뒤에서 runtime error가 발생하지 않으므로, 범위를 벗어나는 조건을 먼저 제외시켜주자.

 

결론적으로 아직 index를 가지고 노는 것이 힘든 것 같다. index를 다룰 때 좀 더 신경써서 생각을 한 다음 코딩을 해야겠다.

 

코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
 
int n, l;
int map[100][100];
 
bool check(vector<int> &d) {
    //중복 안되도록 체크하는 배열
    bool c[100];
    memset(c, false, sizeof(c));
    //오른쪽으로 쭉 가면서 검사한다.
    for (int i = 1; i < n; i++) {
        //차이가 1이상이면 false
        int diff = abs(d[i] - d[i - 1]);
        if (diff > 1)return false;
        //1차이면 어디가 높은 쪽인지 체크한다.
        if (diff == 1) {
            //높아질 때
            if (d[i] > d[i - 1]) {
                //l만큼 가서 계속 높이가 같은지 본다.
                for (int j = 1; j <= l; j++) {
                    //범위 벗어나면 못 놓는다.(항상 범위를 벗어나는 것을 먼저 제외시켜 줘야 runtime error가 발생하지 않는다. 조심하자)
                    if (i - j < 0)return false;
                    //높이가 다르면 경사로 못 놓는다. i-1를 기준으로 해서 높이가 다른지만 체크하면 된다. 왼쪽으로 이동하면서 2칸씩 비교할 필요가 없다.
                    if (d[i - 1] != d[i - j]) return false;
                    //이미 놓여있으면 못 놓는다.
                    if (c[i - j])return false;
                    c[i - j] = true;
                }
            }//높아질 때
            else {
                for (int j = 0; j < l; j++) {
                    if (i + j >= n)return false;
                    if (d[i] != d[i + j]) return false;
                    if (c[i + j])return false;
                    c[i + j] = true;
                }
            }
        }
    }
    return true;
}
 
int main(int argc, char** argv) {
    int ans = 0;
    cin >> n >> l;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    //행 먼저 검사
    for (int i = 0; i < n; i++) {
        vector<int>d;
        for (int j = 0; j < n; j++){
            d.push_back(map[i][j]);
        }
        if (check(d))ans++;
    }
    //열 검사
    for (int i = 0; i < n; i++) {
        vector<int>d;
        for (int j = 0; j < n; j++) {
            d.push_back(map[j][i]);
        }
        if (check(d))ans++;
    }
 
    printf("%d\n", ans);
 
    return 0;
}