[BOJ] 백준 14890. 경사로

문제

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

 

---

풀이

빡 구현 문제입니다. 아이디어는 시간이 있다면 쉽게 떠올려지는데, 조건을 꼼꼼하게 점검해야하는 문제였습니다.

 

우선 경사면을 두 가지로 나누어 볼 수 있습니다. 앞의 계단이 높아서 올라가야하는 경사면과 낮아서 내려가야하는 경사면입니다.

 

올라가야하는 경사면에서는 현재의 위치에서 뒤로 L만큼 체크하며 경사면을 놓을 수 있는지 체크를 해야하고, 내려가야하는 경사면에서는 현재의 위치 다음부터 L만큼 앞으로 체크하며 경사면을 놓을 수 있는지 체크합니다. 

 

 그리고 경사면이 있는 위치에서는 경사면을 놓으면 안됩니다. 경사면이 있는 위치에서 경사면을 놓는 경우는 내려갔다가 올라가는 경우입니다. 이때 경사면을 slope 배열에 저장해 체크했습니다.

 

 아래는 소스 코드입니다. 주석을 통해 부가적인 설명을 추가했습니다.

 

---

소스 코드

import java.util.ArrayList;
import java.util.Objects;
import java.util.Scanner;

public class Main {
    static int N,L;
    static int[][] map;
    static boolean[][] isSlope;
    static int ans = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        map = new int[N][N];

        for(int r = 0;r<N;r++){
            for(int c= 0;c<N;c++){
                map[r][c] = sc.nextInt();
            }
        }
        
        for(int r =0;r<N;r++){
            isSlope = new boolean[N][N]; // 경사면 배열 초기화
            findColPath(r,0,1); // col 방향으로 길 찾기 시작
        }
        for(int c =0;c<N;c++){
            isSlope = new boolean[N][N];
            findRowPath(0,c,1); // row 방향으로 길 찾기 시작
        }
        System.out.println(ans);
    }

    static void findColPath(int row,int col,int same){
        int cur = map[row][col]; //현재 위치
        if(col == N-1) { // 길 끝까지 다 온 것이라면 조건에 부합
            ans++;
        }
        else{
            int next = map[row][col+1]; //다음 위치
            if(Math.abs(next-cur)>=2) return; //만약 차이가 2 이상이면 끝
            if(next == cur) findColPath(row, col+1,same+1); //같다면, 이동
            else if(next==cur-1){ //다음 계단이 -1 이라면,
                if(checkColDown(row, col)){ //경사면 가능한지 체크
                    isSlope[row][col+L] = true; // 경사면 체크
                    findColPath(row, col+L,1); //L만큼 이동
                }
            }
            else if(next==cur+1){ //다음 계단이 +1 이라면 경사면 체크 후 +1 이동
                if(checkColUp(row,col,same)) findColPath(row, col+1,1);
            }
        }
    }
    
    static boolean checkColDown(int row, int col){ //아래로 향하는 경사면 체크
        for(int i = 1;i<=L;i++){ // 현재 위치의 앞부분을 체크한다. 경계를 벗어났는지, 이어지는지.
            if(col+L>=N||map[row][col+1]!=map[row][col+i]) return false;
        }
        return true;
    }

    static boolean checkColUp(int row, int col, int same){ //위로 향하는 경사면 체크
        if(col-L+1<0||same<L) return false; //위로 향하는 것은 뒤를 체크한다. 만약 연속된 수가 경사면 L보다 작으면 false임
        for(int i = 0;i<L;i++){
            if(isSlope[row][col-i]) return false; //뒤를 체크하며 경사면이 있는지 체크 있으면 false
        }
        return true;
    }


    static void findRowPath(int row,int col,int same){ //row도 위와 마찬가지로 진행한다
        int cur = map[row][col];
        if(row == N-1) {
            ans++;
        }
        else{
            int next = map[row+1][col];
            if(Math.abs(next-cur)>=2) return;
            if(next == cur) findRowPath(row+1, col,same+1);
            else if(next==cur-1){
                if(checkRowDown(row, col)){
                    isSlope[row+L][col] = true;
                    findRowPath(row+L, col,1);
                }
            }
            else if(next==cur+1){
                if(checkRowUp(row,col,same)) findRowPath(row+1, col,1);
            }
        }
    }

    static boolean checkRowDown(int row, int col){
        for(int i = 1;i<=L;i++){
            if(row+L>=N||map[row+1][col]!=map[row+i][col]) return false;
        }
        return true;
    }

    static boolean checkRowUp(int row, int col, int same){
        if(row-L+1<0||same<L) return false;
        for(int i = 0;i<L;i++){
            if(isSlope[row-i][col]) return false;
        }
        return true;
    }
}