백준 14890번 : 경사로 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

경사로 골드 3

 

📖 문제

 

 

구현 문제

 

높이 차가 1인 각 칸의 연결을 어떻게 해결하는가가 관건

한쪽 방향이 아닌 양쪽에서 높이차를 두었을때 어떻게 해결할 것인가

단, 높이가 1을 초과한다면 지나갈 수 없다.

 

 

행은 행끼리

열은 열끼리 문제를 나눠 풀되 로직은 같다.

 

 

행을 기준으로

A행이라고 가정하고

 

A 행의 0열을 이전값으로 삶고

A행의 1열과 비교해서 같다면 같은 수를 센다.

 

현재보다 높이가 높은 다음 칸을 만날경우

여태 센 같은 수의 개수가 경사로의 설치 기준 개수를 넘어선다면 

높이가 높은 칸을 자연스럽게 지나가면 된다. 

 

반대로 

현재보다 높이가 낮은 다음 칸을 만날 경우

다음칸부터 다음칸의 같은 높이를 가지는 연속된 칸들의 개수를 센다.

그 수가 경사로 설치 기준 개수를 넘어선다면

경사로를 설치하고 난 이후의 위치로 이동하면된다.

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    //  14890번 경사로
    static int n, l;
    static int[][] arr;

    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());

        arr = new int[n][n];

        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());
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (checkColLine(arr[i][0], i)) answer++;
            if (checkRowLine(arr[0][i], i)) answer++;
        }

        System.out.println(answer);


    }

    private static boolean checkColLine(int prev, int fixRow) {
        int cnt = 1;
        int col = 1;
        while (col < n) {
            // 높이 차가 1보다 크다면 불가능
            if (Math.abs(prev - arr[fixRow][col]) > 1) return false;

            // 이전 값이 현재 값보다 작다면
            if (prev < arr[fixRow][col]) {
                prev = arr[fixRow][col];

                if (cnt >= l) cnt = 1;
                else return false;

                // 현재가 더 높다면
            } else if (prev > arr[fixRow][col]) {

                // 현재~ 현재 + l 까지 설치 가능한지 확인
                int temp = arr[fixRow][col];
                int tempCnt = 1;

                for (int j = col + 1; j < n; j++) {
                    if (temp != arr[fixRow][j]) break;

                    tempCnt++;
                }

                // 설치가능이라면
                if (tempCnt >= l) {
                    prev = arr[fixRow][col]; // 이전값은 현재 값으로
                    col += l; cnt = 0; //col + l 위치부터 시작하므로 col+l부터 탐색하게 0으로 초기화
                    continue;
                }
                // 설치 불가능이라면 이 행은 불가능
                return false;

            } else {
                cnt++;
            }

            col++;
        }

        return true;
    }
    private static boolean checkRowLine(int prev, int fixCol) {
        int cnt = 1;
        int row = 1;

        while (row < n) {
            // 높이 차가 1보다 크다면 불가능
            if (Math.abs(prev - arr[row][fixCol]) > 1) return false;

            // 이전 값이 현재 값보다 작다면
            if (prev < arr[row][fixCol]) {
                prev = arr[row][fixCol];

                // 설치가능하다면 설치하고 이동
                if (cnt >= l) cnt = 1;
                else return false;


                // 현재가 더 높다면
            } else if (prev > arr[row][fixCol]) {

                // 현재~ 현재 + l 까지 설치 가능한지 확인
                int temp = arr[row][fixCol];
                int tempCnt = 1;

                for (int j = row + 1; j < n; j++) {
                    if (temp != arr[j][fixCol]) break;

                    tempCnt++;
                }

                // 설치가능이라면
                if (tempCnt >= l) {
                    prev = arr[row][fixCol]; // 이전값은 현재 값으로
                    row += l; cnt = 0;
                    continue;
                }

                // 설치 불가능이라면 이 행은 불가능
                return false;

            } else {
                cnt++;
            }
            row++;
        }
        return true;
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  항상 인덱스를 확 넘어갈때는 뭔가를 세는 것이 정확한지, 인덱스를 넘기고 추가적으로 연산이 더 들어가는건 아닌지 잘 확인하자.