백준 14890번 경사로 (C++)

문제 링크 : www.acmicpc.net/problem/14890

14890번: 경사로

문제 풀이는 다음과 같다. 

1. n과 l이외에 아래와 같이 변수들을 선언한다.

이때 포인트는 가로열과 세로열의 방문 여부를 확인할 bool문형 배열이다.

int arr[MAX][MAX],n,l, ans = 0;
bool row[MAX][MAX], col[MAX][MAX], ch; // ch ? true : false = 다리 못넣는다 : 넣는다

2. 배열의 값을 입력 받은 뒤 가로줄 먼저 판단을 진행한다.

    for(int i=1; i<=n; i++){ // row 
        ch = false;
        for(int j=2; j<=n; j++){
            if(arr[i][j-1]==arr[i][j]) continue;
            else{ // 경사로 넣기
                if(abs(arr[i][j]-arr[i][j-1])!=1) ch = true;
                else ch = possible(i,j);
            }
            if(ch) break;
        }
        if(!ch) ans++;
    }

만약 이전 차례의 값과 현재 차례의 값이 동일하면 계속 for문을 진행해주면 된다.

그렇지 않을 경우, 두 값의 차이가 1이 아닐 경우에는 ch를 true로 바꿔준다. 그리고 for문을 빠져나온다.

만약 두 값의 차이가 1일 경우, 경사로를 넣을 수 있는지 아닌지 possible 함수를 통해 ch의 값을 정해준다.

 

결론적으로 ch가 false로 판별될 경우에만 경사로를 설치할 수 있다.

 

3. 아래는 가로열의 경사로 설치 여부를 결정하는 함수이다.

아래 코드에서 볼 수 있듯이, 가로줄의 경우 경사로를 왼쪽에 넣는지 오른쪽에 넣는지가 나뉘어진다.

bool possible(int y, int x){
    if(arr[y][x-1]>arr[y][x]){ // 2(x-1),1(x)
        for(int i=x+1; i<x+l; i++){
            if(row[y][i]) return true; // (1)
            if(arr[y][x]!=arr[y][i]) return true; // (2) 
            else row[y][i] = true; // (3)
        }
        if(x+l<=n){
            if(arr[y][x]<arr[y][x+l]) return true; // (4)
        }
    }
    else{ // 1(x-1),2(x)
        for(int i=x-2; i>=x-l; i--){
            if(row[y][i]) return true;
            if(arr[y][x-1]!=arr[y][i]) return true;
            else row[y][i] = true;
        }
        if(x-l-1>=1){
            if(arr[y][x-1]<arr[y][x-l-1]) return true;
        }
    }
    return false;
}

4. 핵심 포인트는 다음과 같다.

    if(arr[y][x-1]>arr[y][x]){ // 2(x-1),1(x)
        for(int i=x+1; i<x+l; i++){
            if(row[y][i]) return true; // (1)
            if(arr[y][x]!=arr[y][i]) return true; // (2) 
            else row[y][i] = true; // (3)
        }
        if(x+l<=n){
            if(arr[y][x]<arr[y][x+l]) return true; // (4)
        }
    }

만약 다음과 같은 높이의 한 줄이 있다고 가정하자.

n = 4이고 l = 2라고 가정해보자.

아래 그래프의 위는 arr[y][x]의 값, 아래는 x의 인덱스이다.

2	1	1	2
x = 0	x = 1	x = 2	x = 3

x가 1일 경우, x+1 = 2부터 for문이 진행된다.

arr[y][x] = 1이고 arr[y][x+1]도 1이다. 때문에 arr[y][x+1]은 true로 변경된다.

그리고 for문은 종료된다.

하지만 잘 생각해보자, x+l이 해당되는, 즉, x+2 = 3의 값은 2이다.

만약 아래 그림과 같은 경우에도 경사로를 넣을 수 있을까?

 

 

 

당연하지만 안된다. 때문에 (4)번 주석에 위치한 판별이 이루어져야한다.

 

5. 다시 코드로 돌아가보자.

이번에는 앞에서 설명하지 못했던 (1)번 주석을 들여다보자.

    if(arr[y][x-1]>arr[y][x]){ // 2(x-1),1(x)
        for(int i=x+1; i<x+l; i++){
            if(row[y][i]) return true; // (1)
            if(arr[y][x]!=arr[y][i]) return true; // (2) 
            else row[y][i] = true; // (3)
        }
        if(x+l<=n){
            if(arr[y][x]<arr[y][x+l]) return true; // (4)
        }
    }

 

 

 

만약 앞 부분에서 성공적으로 판별이 이루어져 경사로가 설치됐다고 가정해보자.

그 다음 for문을 검사할때, 아래 그림과 같은 상황이 이루어질 수 있을까?

 

 

결론적으로 안된다. 이미 경사대가 설치된 부분에 또 다른 경사대를 설치할 수 없다.

때문에 bool문으로 검사가 이루어져야한다,

 

6. 위의 row를 검사하는 핵심 코드는 세로줄은 col에도 동일하게 적용된다.

다만 값의 범위를 잡는 부분에서만 차이가 발생하므로, 이 점만 주의하면 된다.

 

#include <iostream>
#define MAX 101
using namespace std;

int arr[MAX][MAX],n,l, ans = 0;
bool row[MAX][MAX], col[MAX][MAX], ch; // true = 다리 못넣는다

bool possible(int y, int x){
    if(arr[y][x-1]>arr[y][x]){ // 2(x-1),1(x)
        for(int i=x+1; i<x+l; i++){
            if(row[y][i]) return true;
            if(arr[y][x]!=arr[y][i]) return true; // 다리 못넣는다
            else row[y][i] = true;
        }
        if(x+l<=n){
            if(arr[y][x]<arr[y][x+l]) return true;
        }
    }
    else{ // 1(x-1),2(x)
        for(int i=x-2; i>=x-l; i--){
            if(row[y][i]) return true;
            if(arr[y][x-1]!=arr[y][i]) return true;
            else row[y][i] = true;
        }
        if(x-l-1>=1){
            if(arr[y][x-1]<arr[y][x-l-1]) return true;
        }
    }
    return false;
}

bool possible2(int y, int x){ // 2
    if(arr[y-1][x]>arr[y][x]){ // 1 (y)
        for(int i=y+1; i<y+l; i++){
            if(col[y][i]) return true;
            if(arr[y][x]!=arr[i][x]) return true; // 다리 넣기 실패
            else col[i][x] = true;
        }
        if(y+l<=n){
            if(arr[y][x]<arr[y+l][x]) return true;
        }
    }     // 1
    else{ // 2 (y)
        for(int i=y-2; i>=y-l; i--){
            if(col[i][x]) return true;
            if(arr[y-1][x]!=arr[i][x]) return true;
            else col[i][x] = true;
        }
        if(y-l-1>=1){
            if(arr[y-1][x]<arr[y-l-1][x]) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> l;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) cin >> arr[i][j];
    }
    for(int i=1; i<=n; i++){ // row 
        ch = false;
        for(int j=2; j<=n; j++){
            if(arr[i][j-1]==arr[i][j]) continue;
            else{ // 경사로 넣기
                if(abs(arr[i][j]-arr[i][j-1])!=1) ch = true;
                else ch = possible(i,j);
            }
            if(ch) break;
        }
        if(!ch) ans++;
    }
    for(int i=1; i<=n; i++){ // col
        ch = false;
        for(int j=2; j<=n; j++){
            if(arr[j][i]==arr[j-1][i]) continue;
            else{ // 경사로 넣기
                if(abs(arr[j][i]-arr[j-1][i])!=1) ch = true;
                else ch = possible2(j,i);
            }
            if(ch) break;
        }
        if(!ch) ans++;
    }
    cout << ans << "\n";
    return 0;
}