[BOJ] 14890. 경사로

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

접근 방법

N의 크기가 크지 않아서 그냥 완전 탐색을 하기로 했다.

행 검사 따로 . 열 검사 따로 하기로 했다.

먼저 행을 검사할 때

1. 지금 값과 그 전의 값의 차이가 2라면 그냥 해당 행에 대해 검사하지 않고 Pass

    if(Math.abs(map[i][k]-map[i][k-1])>1){
                        flag = false;
                        break;
                    }

2. 지금 값보다 그 전의 값이 크다면 ( F(n-1) > F(n) )

   앞으로의 값들을 체크해줘야한다.

   여기서 경사로는 서로 겹치면 안되기 때문에 visit배열에 체크를 해줬다.

    if(map[i][k-1] - map[i][k] == 1){
                        if(k+L-1 >= N){
                            flag = false;
                            break;
                        }
                        for(int l = k; l<= k+L-1; l++){
                            if(map[i][k-1]-1 != map[i][l] || visit[i][l]){
                                flag = false;
                                break z;
                            }else{
                                visit[i][l] = true;
                            }
                        }
                        continue;
                    }

3. 지금 값이 그 전의 값보다 크다면 ( F(n-1) < F(n) )

    if(map[i][k-1] - map[i][k] == -1){
                        if(k-L < 0){
                            flag = false;
                            break;
                        }
                        for(int l = k-L; l<k; l++){
                            if(map[i][k]-1 != map[i][l] || visit[i][l]){
                                flag = false;
                                break z;
                            }else{
                                visit[i][l] = true;
                            }
                        }
                        continue;
                    }

Need Know

1. 음..? 구현?

전체 코드 ( Java )

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int L;
    static int[][] map;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int k=0;k<N; k++){
                map[i][k] = Integer.parseInt(st.nextToken());
                // 가로 체크
            }
        }
    }

    static void solve() throws IOException {
       bw.write((checkRow()+checkCol()) +"");
    }
    static int checkRow(){
        visit = new boolean[N][N];
        int result = 0 ;
        for(int i=0; i<N; i++){
            boolean flag = true;
            z:for(int k=1; k<N; k++) {
                if(Math.abs(map[i][k]-map[i][k-1])>1){
                    flag = false;
                    break;
                }
                // 앞에가 더 크다.
                if(map[i][k-1] - map[i][k] == 1){
                    if(k+L-1 >= N){
                        flag = false;
                        break;
                    }
                    for(int l = k; l<= k+L-1; l++){
                        if(map[i][k-1]-1 != map[i][l] || visit[i][l]){
                            flag = false;
                            break z;
                        }else{
                            visit[i][l] = true;
                        }
                    }
                    continue;
                }
                // 뒤에가 더 크다.
                if(map[i][k-1] - map[i][k] == -1){
                    if(k-L < 0){
                        flag = false;
                        break;
                    }
                    for(int l = k-L; l<k; l++){
                        if(map[i][k]-1 != map[i][l] || visit[i][l]){
                            flag = false;
                            break z;
                        }else{
                            visit[i][l] = true;
                        }
                    }
                    continue;
                }
            }
            if(flag){
                result++;
            }
        }
        return result;
    }
    static int checkCol(){
        visit = new boolean[N][N];
        int result = 0 ;
        for(int i=0; i<N; i++){
            boolean flag = true;
            z:for(int k=1; k<N; k++) {
                if(Math.abs(map[k][i]-map[k-1][i])>1){
                    flag = false;
                    break;
                }
                // 위에가 더 크다.
                if(map[k-1][i]-map[k][i] == 1){
                    if(k+L-1 >= N){
                        flag = false;
                        break;
                    }
                    for(int l = k; l<= k+L-1; l++){
                        if(map[k-1][i]-1 != map[l][i] || visit[l][i]){
                            flag = false;
                            break z;
                        }else{
                            visit[l][i] = true;
                        }
                    }
                    continue;
                }
                // 밑에가 더 크다.
                if(map[k-1][i] - map[k][i] == -1){
                    if(k-L < 0){
                        flag = false;
                        break;
                    }
                    for(int l = k-L; l<k; l++){
                        if(map[k][i]-1 != map[l][i] || visit[l][i]){
                            flag = false;
                            break z;
                        }else{
                            visit[l][i] = true;
                        }
                    }
                    continue;
                }
            }
            if(flag){
                result++;
            }
        }
        return result;
    }
}