백준 14890번: 경사로

문제 설명

• https://www.acmicpc.net/problem/14890
• 길이가 L, 높이가 1인 경사로를 통해 길을 지나갈 수 있는지 구하는 문제입니다.
• 경사로는 일정한 조건으로만 놓을 수 있습니다.

접근법

• 배열을 입력받으면 경사로를 놓을 수 있는지를 판별하는 메서드가 필요하다고 생각했습니다.
• 경사로의 종류는 2개(올라가는 경사로와 내려가는 경사로)이기 때문에 조건에 따라 다른 경사로를 활용해야 합니다.
• 경사로를 활용할 수 없는 조건을 잘 판단해야 합니다.
  • 높이차이가 2이상이면 길을 건널 수 없습니다.
  • 이미 경사로를 놓은 칸 위에 또다시 경사로를 만들 수 없습니다.
    • 해당 칸에 경사로가 놓였는지 판단하는 v배열을 만들었습니다.

pseudocode

Main(){
	모든 행 배열과 열 배열에 대해 SlideCheck를 진행.
}
SlideCheck(배열){
	for(i=0부터N-1까지){
    	if(i번째 값과 i+1번째 값이 2 이상 차이나면) return false
    	if(i번쨰 칸에 올라가는 경사로와 내려가는 경사로를 모두 놓아야 하는 상황이면) return false
        if(i번째 값보다 i+1번째 값이 1 크면){ // 올라가는 경사로가 필요하면
        	if(!UpSlideCheck) return false // 올라가는 경사로를 못놓으면 false
            올라가는 경사로를 놓을 수 있으면 해당 칸들을 중복사용 못하게 방문처리    
        }
        if(i번째 값보다 i+1번쨰 값이 1 작으면){ // 내려가는 경사로가 필요하면
        	if(!DownSlideCheck) return false // 내려가는 경사로를 못놓으면 false
        }        
    }
    return true //못놓는 경우를 모두 피해갔으면 해당 배열은 길로 지나갈 수 있음.
}
UpSlideCheck(){
	if(놓아야 하는 곳이 배열 밖이면) return false;
    for(now를 포함한 왼쪽 L개의 블록을 검사하면서){
    	if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
    }
}
DownSlideCheck(){
	if(놓아야 하는 곳이 배열 밖이면) return false;
    for(now를 포함한 오른쪽 L개의 블록을 검사하면서){
    	if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
    }
}

정답

import java.util.*;

public class Main {
	static int N, L, Score;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		for (int i = 0; i < N; i++) {
        	//열 배열을 구합니다
			int[] colArr = new int[N];
			for (int j = 0; j < N; j++) {
				colArr[j] = board[j][i];
			}
            // 행 배열 길을 건널 수 있는지 체크합니다.
			if (SlideCheck(board[i]))
				Score++;
            // 열 배열 길을 건널 수 있는지 체크합니다.
			if (SlideCheck(colArr))
				Score++;
		}
		System.out.println(Score);
	}

	public static boolean SlideCheck(int[] arr) {
		boolean[] v = new boolean[N];
        // 해당 칸(i)과 다음 칸(i+1)의 값이 다른지 비교합니다.
		for (int i = 0; i < N - 1; i++) {
        	// 2칸 이상 차이가 나면 길을 건널 수 없습니다.
			if (Math.abs(arr[i] - arr[i + 1]) >= 2)
				return false;
            // 내려가는 경사로와 올라가는 경사로를 동시에 요구하는 길은 결국 건널 수 없는 길입니다.
			if ((i < N && arr[i] < arr[i + 1] && UpSlideCheck(arr, i, v))
					&& (i > 0 && arr[i - 1] > arr[i] && DownSlideCheck(arr, i + 1, v))) {
				return false;
			}
            // 올라가는 경사로가 필요합니다.
			if (arr[i] < arr[i + 1]) {
            	// 올라가는 경사로를 설치할 수 없다면 false를 반환합니다.
				if (!UpSlideCheck(arr, i, v))
					return false;
                // 올라가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
				for (int j = i - L + 1; j <= i; j++) {
					v[j] = true;
				}
			}
            // 내려가는 경사로가 필요합니다.            
			if (arr[i] > arr[i + 1]) {
            	// 내려가는 경사로를 설치할 수 없다면 false를 반환합니다.            
				if (!DownSlideCheck(arr, i + 1, v))
					return false;
                // 내려가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
				for (int j = i + 1; j <= i + 1 + L - 1; j++) {
					v[j] = true;
				}
			}
		}
		return true;
	}

	public static boolean UpSlideCheck(int[] arr, int now, boolean[] v) {
		// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
		if (now - L + 1 < 0)
			return false;
        // now를 포함한 왼쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
		int Std = arr[now];
		for (int i = now - L + 1; i < now; i++) {
			if ((arr[i] != Std) || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
				return false;
		}
		return true;

	}

	public static boolean DownSlideCheck(int[] arr, int now, boolean[] v) {
		// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
		if (now + L - 1 >= N)
			return false;
        // now를 포함한 오른쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
		int Std = arr[now];
		for (int i = now; i <= now + L - 1; i++) {
			if (arr[i] != Std || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
				return false;
		}
		return true;

	}
}