[백준 Baekjoon] 14890번 경사로 - JAVA

백준 Baekjoon 14890번 경사로 - JAVA

---

문제 풀이

어떠한 알고리즘을 적용하는 것이 아니라 구현을 통해 풀어야 하는 문제이다.


입력받은 지도에서 모든 행과 열을 검사하여 경사로를 놓아 길을 지날 수 있는지 검사해야 한다.

1. 다음 칸과의 높이 차가 1이상인 경우 경사로를 놓을 수 없다.
2. 내리막길인 경우(현재 칸 - 다음 칸 = 1), 오르막길인 경우(다음 칸 - 현재 칸 = 1) 경사로를 놓기 위해 필요한 L개의 칸을 검사하여 경사로를 놓을 수 있는지 검사한다.
3. 1 내리막길인 경우 다음 칸부터 다음 L개의 칸을 검사한다.
4. 2 오르막길인 경우 현재 칸부터 이전 L개의 칸을 검사한다.
5. 이미 경사로를 놓은 칸에 경사로를 놓을 수 없다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N, L;
    public static int[][] map;

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

        StringTokenizer 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 answer = 0;

        for (int i = 0; i < N; i++) {
            if (isValid(i, 0, 0)) { // 행 검사
                answer++;
            }

            if (isValid(0, i, 1)) { // 열 검사
                answer++;
            }
        }

        System.out.println(answer);
    }

    public static boolean isValid(int x, int y, int d) {
        int[] arr = new int[N];
        boolean[] visit = new boolean[N]; // 경사로 놓은지 유무

        for (int i = 0; i < N; i++) {
            arr[i] = d == 0 ? map[x][y + i] : map[x + i][y];
        }

        for (int i = 0; i < N - 1; i++) {
            if (Math.abs(arr[i] - arr[i + 1]) > 1) { // 차가 1 이상인 경우
                return false;
            } else if (arr[i] - arr[i + 1] == 1) { // 내리막길
                for (int j = i + 1; j <= i + L; j++) {
                    if (j >= N || arr[i + 1] != arr[j] || visit[j]) {
                        return false;
                    }

                    visit[j] = true;
                }
            } else if (arr[i + 1] - arr[i] == 1) { // 오르막길
                for (int j = i; j > i - L; j--) {
                    if (j < 0 || arr[i] != arr[j] || visit[j]) {
                        return false;
                    }

                    visit[j] = true;
                }
            }
        }

        return true;
    }
}