[beakjoon] 14890 경사로 java

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

14890번: 경사로

이 문제는 주어진 조건을 잘 거르고 양방향 설치가 가능하다는 점에 유의하면 된다.

 

시작점은 위거나 제일 왼쪽에서 시작.

나의 경우엔 배열을 일일이 만들어줘서 공통 메서드(route)에서 풀이하였다.

배열에서 인덱스값이 커지는 순서대로 파악하되, 앞뒤 값의 차가 1이면 경사로를 설치할 수 있는 길이가 되는지 확인한다.

앞뒤 차가 0이면 계속 탐색, 2 이상이면 경사로를 지을 수 없다.

경사로는 양방향이 가능한데 이 부분이 이 문제의 포인트라 생각한다. 경사로를 설치하려면, 오르막인지 내리막인지 확인을 해줘야 한다.

즉, 방향을 알아야 한다.

왼쪽의 높이가 더 크다면 내리막이기에 오른쪽을 향해 경사로를 지을 길이가 나오는지 확인해준다.

반대로 왼쪽 높이가 더 높다면 오르막이기에 왼쪽에 경사로를 지을 여유 거리가 있는지 확인해 줘야 한다.

 

이 문제에서 주의해야할 조건들을 정리하자면,

1. 인접한 칸들간의 높이 확인

2. 인접한 칸들의 길이 확인

-> 확인하며 배열의 길이를 벗어나지 않는지 확인.

3. 경사로가 연속해서 지어질 수 없기에 바로 앞에 경사로가 있는지 확인

 

 

import java.io.*;
import java.util.*;
 
class Main {
    static int L, N;
    static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int cnt = 0;
        
        for (int i = 0; i < N; i++) {
            int[] arr = new int[N];
            for (int j = 0; j < N; j++) {
                arr[j] = map[i][j];
            }
            if (route(arr)) {
                cnt++;
            }
        }
        
        for (int i = 0; i < N; i++) {
            int[] arr = new int[N];
            for (int j = 0; j < N; j++) {
                arr[j] = map[j][i];
            }
            if (route(arr)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
 
    public static boolean route(int[] arr) {
        boolean[] slide = new boolean[N];
        for (int i = 0; i < N-1; i++) {
            int prev = arr[i];
            int cur = arr[i+1];
            int step = cur - prev;
            if (step == 0)
                continue;
            if (Math.abs(step) > 1)
                return false;
 
            if (step < 0) { //내리막길(현재 위치 다음부터 길이가 되는지 확인해야 하기 때문에 1부터 시작)
                for (int j = 1; j <= L; j++) {
                    if (i + j >= N)
                        return false;
                    if (slide[i + j])
                        return false;
                    if (arr[i + 1] != arr[i + j])
                        return false;
                    slide[i + j] = true;
                }
            } else {//오르막길(현재 위치부터 역으로 길이가 되는지 확인해야 하기에 0부터 시작)
                for (int j = 0; j < L; j++) {
                    if (i - j < 0)
                        return false;
                    if (slide[i - j])
                        return false;
                    if (arr[i] != arr[i - j])
                        return false;
                    slide[i - j] = true;
                }
            }
        }
 
        return true;
    }
}