백트래킹(14890 경사로)

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

14890번: 경사로

 

모든 행에 대해서 왼쪽에서 오른쪽으로 진행하며 지나갈 수 있는 길인지 확인하는 방식으로 문제를 풀었다.

---

✅왼쪽 블럭과의 높이 차이(gap) 계산

• gap == 0 : 다음 칸으로 재귀
• gap == 1 : 왼쪽 블럭에 계단을 놓을 수 있는지 확인한 후 다음 칸으로 재귀
• gap == -1 : 이면 오른쪽 블럭에 계단을 놓을 수 있는지 확인한 후 계단 이후 칸으로 재귀

 

✅백트래킹 종료(basecase) 조건

• 계단을 마지막 블럭에 딱 맞게 놓고, 재귀함수를 탄 경우 : 지나갈 수 있는 길 이므로 ans+=1
• 현재 탐색 위치가 마지막 블럭인 경우
  • gap == 0 : 지나갈 수 있는 길 이므로 ans+=1
  • gap == 1 : 왼쪽 블럭에 계단을 놓을 수 있으면 ans+=1
  • gap == -1 : 계단의 길이가 1이면 ans+=1

 

---

코드 구현

 

💡왼쪽 블럭에 계단을 놓을 여분의 자리가 있는지 확인하기 위해 함수의 매개변수 cnt를 활용했다.

static void check(int[][] array,int row,int col,int cnt){

}

cnt : 현재 위치 col에서 계단을 놓을 수 있는 길이를 뜻한다.

gap == 0 : 계단을 놓을 수 있는 길이가 1 증가 하므로 check(array,row,col+1,cnt+1) 

gap == 1 :  col+1 위치에서 계단을 놓을 수 있는 길이는 1이므로 check(array,row,col+1,1)

gap == -1 : col+L 위치에서 계단을 놓을 수 있는 길이는 0이므로 check(array,row,col+L,0)

 

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;


public class Main {

    static int N,L;
    static int[][] arr;
    static int ans;

    static void check(int[][] array,int row,int col,int cnt){ // cnt : 계단을 놓을 수 있는 블럭의 크기

        if(col==N){ // 계단을 마지막 블럭에 딱 맞게 놓고, 재귀 함수를 탄 경우
            ans+=1;
            return;
        }

        int gap; // 이전 블럭과 높이 차이

        if(col-1<0){ // 함수 시작 입력인 경우 gap=0
            gap = 0;
        }else{
            gap = array[row][col] - array[row][col-1]; // 이전 블럭과 높이 차이
        }

        if(col==N-1){ // 현재 탐색 위치가 마지막 블럭인 경우
            if(gap==0){ // 높이 차가 없는 경우
                ans+=1;
            }
            else if(gap==1 && cnt>=L){ // 현재 블럭이 1만큼 높이 있고, 계단을 놓을 여분의 길이가 있으면
                ans+=1;
            }
            else if(gap==-1 && L==1){ // 현재 블럭이 1만큼 낮게 있고, 계단의 길이가 1인 경우
                ans+=1;
            }
            return;
        }


        if(gap==0){ // 높이 차가 없으면
            check(array,row,col+1,cnt+1); // 다음 블럭으로 재귀
        }else if(gap==1){ // 1만큼 크면
            if(cnt>=L){ // 계단을 놓을 여분의 길이가 있으면
                check(array,row,col+1,1); // cnt가 1인 이유 = col+1 위치에서 계단을 놓을 수 있는 크기가 1이기 때문
            }
        }else if(gap==-1){ // 1만큼 작으면
            int temp = 0;
            for(int c=col;c<N;c++){ // 계단을 놓을 수 있는지 길이 체크
                if(array[row][c]==array[row][col]){
                    if(++temp==L) break;
                }else{
                    break;
                }
            }
            if(temp==L){ // 계단을 놓을 수 있으면
                check(array,row,col+L,0); // cnt가 0인 이유 = col+L 위치에서 직전 블럭에는 계단을 놓을 수 없기 때문
            }
        }
    }

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

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

        arr = new int[N][N];
        ans = 0;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int r=0;r<N;r++){
            check(arr,r,0,0);
        }
        System.out.println(ans);


        // 배열 90도 회전시키기
        int[][] tmp = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                tmp[i][j] = arr[N-1-j][i];
            }
        }

        for(int r=0;r<N;r++){
            check(tmp,r,0 ,0);
        }

        for(int r=0;r<N;r++){
            System.out.println(Arrays.toString(tmp[r]));
        }
        System.out.println(ans);

    }

}