[백준]14890: 경사로 - JAVA

[백준]14890: 경사로

14890번: 경사로

풀이

🪑 조건에 따라 문제를 잘 읽고 풀어야 하는 구현 문제였다.

 

확인해 주어야 할 방향은 총 2가지 방향이므로 (열, 행) 열을 확인하는 함수, 행을 확인하는 함수 두개로 나누어 풀어주었다.

 

🔎 확인할때는 한 방향으로 확인하며 현재 계단의 높이와 다음 계단의 높이차를 확인해 주었다.

계단의 높이차가 1을 초과하면 문제의 조건에 나와있는 "계단의 높이차는 1이어야 한다"를 만족하지 못하므로 바로 false를 반환하도록 하였다.

 

계단의 높이차가 1이더라도 다음 계단이 현재 계단보다 높은지, 낮은지에 따라 다르게 구현해 주었다.

 

🔹 다음 계단이 현재 계단보다 한 단계 높은 경우. 아래와 같은 경우이다.

이때는 올라가는 경사로를 설치해 주어야 한다. 이때 올라가는 경사로를 설치하는 넓이가 L이상이어야 한다. 

그러므로 L길이만큼 경사로를 설치할 수 있는지 확인해 주면 된다.

 

- 올라가는 경사로를 설치할 수 없는 경우는 아래와 같다.

1. 계단 길이가 경사로를 설치할 길이보다 짧다.
2. 경사로를 설치해야 하는 위치에 이미 경사로가 설치되어 있다.
3. 경사로를 만들어야 하는 길이 만큼 같은 높이의 계단이 있어야 하는데 계단의 높이가 달라진다.

(이미 경사로가 설치되었는지를 체크하기 위해 boolean 배열을 생성해 주었다.)

위의 경우를 제외한 경우에는 경사로를 설치해 주면 된다.

 

🔹 다음 계단이 현재 계단보다 한 계단 낮은 경우. 아래와 같은 경우이다.

이런 경우에는 내려가는 경사로를 설치해 주어야 한다. 현재 계단 다음 계단부터 설치해 주어야 하며 설치하는 넓이는 L이상이어야 한다.

 

- 내려가는 경사로를 설치할 수 없는 경우는 아래와 같다.

1. 경사로 길이보다 계단 길이가 짧다.
2. 경사로를 설치행야 하는 위치에 이미 경사로가 설치되어 있다.
3. 경사로를 만들어야 하는 길이 만큼 같은 높이의 계단이 없다.

위의 경우를 제외한 경우에 경사로를 설치해 주면 된다.

 

열, 행을 확인하며 위의 예외 케이스 중 하나도 만나지 못했다면, 그 열 또는 행은 지나갈 수 있는 길이 된다!

 

코드

import java.util.*;
 
public class Main {
 
    static int n, l;
    static int[][] board;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        l = scan.nextInt();
 
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = scan.nextInt();
            }
        }
 
        int count = 0;
        for(int i = 0; i < n; i++) {
            if(calRow(i)) count++; //i번째 열 확인
            if(calCol(i)) count++; //i번째 행 확인
        }
        System.out.println(count);
    }
 
    public static boolean calRow(int row) {
        boolean[] isIncline = new boolean[n]; //경사면 설치 여부를 확인하는 배열
 
        for(int i = 0; i < n - 1; i++) {
            int diff = board[row][i] - board[row][i + 1];
            
            if(diff > 1 || diff < -1) return false; //높이차 1 초과하므로 false
            else if(diff == -1) { // 다음 계단이 한 계단 높다
                for(int j = 0; j < l; j++) { // 올라가는 경사로를 설치할 수 있는지 확인한다.
                    if(i - j < 0 || isIncline[i - j]) return false;
                    if(board[row][i] != board[row][i - j]) return false;
                    isIncline[i - j]  = true; //경사면 설치
                }
            } 
            else if(diff == 1) { //다음 계단이 한 계단 낮다
                for(int j = 1; j <= l; j++) { //내려가는 경사로를 설치할 수 있는지 확인한다.
                    if(i + j >= n || isIncline[i + j]) return false;
                    if(board[row][i] - 1 != board[row][i + j]) return false;
                    isIncline[i + j] = true; //경사면 설치
                }
            }
        }
        return true;
    }
    
    public static boolean calCol(int col) {
        boolean[] isIncline = new boolean[n]; //경사면 설치 여부를 확인하는 배열
 
        for(int i = 0; i < n - 1; i++) {
            int diff = board[i][col] - board[i + 1][col];
            
            if(diff > 1 || diff < -1) return false; //높이차 1 초과하므로 false
            else if(diff == -1) { // 다음 계단이 한 계단 높다
                for(int j = 0; j < l; j++) { // 올라가는 경사로를 설치할 수 있는지 확인한다.
                    if(i - j < 0 || isIncline[i - j]) return false;
                    if(board[i][col] != board[i - j][col]) return false;
                    isIncline[i - j]  = true; //경사면 설치
                }
            } 
            else if(diff == 1) { //다음 계단이 한 계단 낮다
                for(int j = 1; j <= l; j++) { //내려가는 경사로를 설치할 수 있는지 확인한다.
                    if(i + j >= n || isIncline[i + j]) return false;
                    if(board[i][col] - 1 != board[i + j][col]) return false;
                    isIncline[i + j] = true; //경사면 설치
                }
            }
        }
        return true;
    }
}