[백준] 14890. 경사로

문제

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

풀이

배열이 나와서 완전탐색 문제인가 싶었지만 시뮬레이션 문제였다. 실수가 많아서 시간이 좀 걸렸다. 배열을 초기화하지 않아서 이상한 값이 들어가 틀리고, 배열에 들어갈 수 있는 범위를 체크해주지 않아서 런타임 에러가 뜨고, 경사로를 겹쳐도 되게 만들어서 틀리고... 항상 조건을 잘 파악하고, 알고리즘을 짤 때 내가 생각한대로 나오는지 꼼꼼히 체크하도록 하자. 기본적인 아이디어는 다음과 같다.

• 배열의 각 행의 0번부터 n - 1번까지 체크해준다. 
• 체크 중에 현재 인덱스의 높이와 이전의 높이가 다를 때, 세가지 경우로 다시 나눠준다.

1. 현재 높이가 이전 높이보다 크다면, 경사의 길이만큼 이전의 개수를 체크해서 높이가 다 같은지 확인하고, 다 같으면 경사로를 깔아준다. 그렇지 않다면 전체 answer 개수를 1개 빼주고 현재 행에 대한 탐색을 끝낸다.
2. 현재 높이가 이전 높이보다 작다면, 경사의 길이만큼 다음의 개수를 체크해서 높이가 다 같은지 확인하고, 다 같으면 경사로를 깔아준다. 그렇지 않다면 전체 answer 개수를 1개 빼주고 현재 행에 대한 탐색을 끝낸다.
3. 현재 높이와 이전 높이의 차이가 1보다 크면, 전체 answer 개수를 1개 빼주고 현재 행에 대한 탐색을 끝맞춘다.

• 행에 대한 탐색이 모두 끝났으면, 열에 대한 탐색도 위와 똑같이 해준다.

//
//  14890.cpp
//  BJ
//
//  Created by 신기열 on 25/10/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

int map[101][101];
int answer;
int visited[101];
int n, L;

int main(){

    cin >> n >> L;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> map[i][j];
        }
    }
    answer = n * 2;
    // 모든 행에 대하여
    for(int i = 0; i < n; i++){
        //cout << i << "행   :   ";
        int flag = 0;
        // 가로 한줄 쭉 훑어볼 떄
        int j = 1;
        for(int i = 0; i < n; i++){
            visited[i] = 0;
        }
        while(j < n){
            //cout << j << "번째 탐색" << '\n';
            // 높이 : 탐색 기준 왼쪽
            int h = map[i][j - 1];
            // 높이가 같지 않다면
            if(map[i][j] != h){
                // 오른쪽이 왼쪽보다 1 높을 때
                if(map[i][j] == h + 1){
                    for(int k = 1; k <= L; k++){
                        if(j - k < 0 || j - k >= n || (j - k >= 0 && j - k < n && (map[i][j - k] != h || visited[j - k] == 1))){
                            answer--;
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 0){
                        for(int k = 1; k <= L; k++){
                            visited[j - k] = 1;
                        }
                        j++;
                    }
                }
                // 오른쪽이 왼쪽보다 1 낮을 때
                else if(map[i][j] == h - 1){
                    int ch = map[i][j];
                    for(int k = 0; k < L; k++){
                        if(j + k < 0 || j + k >= n || (j + k >= 0 && j + k < n && (map[i][j + k] != ch || visited[j + k] == 1))){
                            answer--;
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 0){
                        for(int k = 0; k < L; k++){
                            visited[j + k] = 1;
                        }
                        j += L;
                    }
                }
                else{
                    answer--;
                    break;
                }
            }
            else j++;
            if(flag == 1){
                j++;
                //cout << "길이 아닙니다.   answer : " << answer <<  '\n';
                break;
            }
        }
    }

    // 모든 열에 대하여
    for(int i = 0; i < n; i++){
        
        //cout << i << "열  :  ";
        int flag = 0;
        // 가로 한줄 쭉 훑어볼 떄
        int j = 1;
        for(int i = 0; i < n; i++){
            visited[i] = 0;
        }
        while(j < n){
            //cout << j << "번째 탐색 : ";
            // 높이 : 탐색 기준 왼쪽
            int h = map[j - 1][i];
            // 높이가 같지 않다면
            if(map[j][i] != h){
                // 오른쪽이 왼쪽보다 1 높을 때
                if(map[j][i] == h + 1){
                    for(int k = 1; k <= L; k++){
                        if(j - k < 0 || j - k >= n || (j - k >= 0 && j - k < n && (map[j - k][i] != h || visited[j - k] == 1))){
                            answer--;
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 0){
                        for(int k = 1; k <= L; k++){
                            visited[j - k] = 1;
                        }
                        j++;
                    }
                }
                // 오른쪽이 왼쪽보다 1 낮을 때
                else if(map[j][i] == h - 1){
                    int ch = map[j][i];
                    for(int k = 0; k < L; k++){
                        if(j + k < 0 || j + k >= n || (j + k >= 0 && j + k < n && (map[j + k][i] != ch || visited[j + k] == 1))){
                            answer--;
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 0){
                        for(int k = 0; k < L; k++){
                            visited[j + k] = 1;
                        }
                        j += L;
                    }
                }
                else{
                    answer--;
                    break;
                }
            }
            else j++;

            if(flag == 1){
                j++;
                //cout << "길이 아닙니다.   answer : " << answer << '\n';
                break;
            }
        }
    }
    
    cout << answer;
    return 0;
}