문제링크

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

구현방법

길이란 한 행 또는 한 열 전부

• 한쪽 끝에서 다른 쪽 끝까지 지나가는 것.

길을 지나가려면 길에 속한 모든 칸의 높이가 같아야하는데 경사로를 놓아서 길을 만들기가 가능.

• 경사로는 높이가 항상 1이다. 길이는 L
  • 개수는 무제한.

경사로의 조건

1. 낮은칸에 놓는다. L 개의 연속된 칸에 경사로의 바닥이 모두 접해야됨.
2. 높은 칸과 낮은 칸의 차이는 1 이여야함 (그외 불가능.)
3. 경사로를 놓는 낮은 칸의 높이는 모두 같아야하며 ,L개의 칸이 연속되야함.

제한 점

• 경사로를 놓은 곳은 또 놓을 수 없다.
• 낮은 지점 칸의 높이가 모두 같지 않거나 L개가 연속이지 않을 경우 놓을 수 없다.
• 범위를 벗어나는 경우

경사로를 놓고서 지나갈 수 있는 길의 개수 구하기.

각 길에 대해서 따로 생각을 하는건가?

잘못 생각했던점

• 처음에 이전에 설치한 경사로도 생각해야하는지 고민이였는데 해결이 되지 않아서 다른 분이 어떻게 풀었나 봤더니 경사로를 다른 곳에 설치한 것은 따로 생각해도되는 문제였다.

이 부분을 해결하니 문제의 난이도가 낮아졌다.

알고리즘

• 구현

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int L;

    static int map[][];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                map[row][col] = Integer.parseInt(st.nextToken());
            }
        }

        int res = 0;
        for (int idx = 0; idx < N; idx++) {
            if (checkRow(idx)) res += 1;
            if (checkCol(idx)) res += 1;
        }

        System.out.println(res);


    }

    private static boolean checkRow(int col) {
        boolean isCheck[] = new boolean[N];


        for (int idx = 0; idx < N - 1; idx++) {
            int diff = map[idx][col] - map[idx + 1][col];


            if (diff > 1 || diff < -1) return false;
                //다음 번호가 값이 높은 경우
            else if (diff == -1) {
                for (int i = 0; i < L; i++) {
                    //설치할 길이가 안나오거나 이미 설치가 되있는 경우
                    if (idx - i < 0 || isCheck[idx - i]) return false;
                    if (map[idx][col] != map[idx - i][col]) return false;
                    isCheck[idx - i] = true;
                }
            }
            //낮은 경우
            else if (diff == 1) {
                for (int i = 1; i <= L; i++) {
                    //범위를 벗어나거나 이미 설치가 된 경우
                    if (idx + i >= N || isCheck[idx + i]) return false;
                    if (map[idx][col] - 1 != map[idx + i][col]) return false;
                    isCheck[idx + i] = true;
                }
            }
        }


        return true;

    }

    private static boolean checkCol(int row) {

        boolean isCheck[] = new boolean[N];

        for (int idx = 0; idx < N - 1; idx++) {
            int diff = map[row][idx] - map[row][idx + 1];

            if (diff > 1 || diff < -1) {
                return false;
            } else if (diff == -1) {
                for (int i = 0; i < L; i++) {
                    //설치할 길이가 안나오거나 이미 설치가 되있는 경우
                    if (idx - i < 0 || isCheck[idx - i]) return false;
                    if (map[row][idx] != map[row][idx - i]) return false;
                    isCheck[idx - i] = true;
                }
            }
            //낮은 경우
            else if (diff == 1) {
                for (int i = 1; i <= L; i++) {
                    //범위를 벗어나거나 이미 설치가 된 경우
                    if (idx + i >= N || isCheck[idx + i]) return false;
                    if (map[row][idx] - 1 != map[row][idx + i]) return false;
                    isCheck[idx + i] = true;
                }
            }


        }


        return true;
    }
}