[백준] 14890: 경사로 - JAVA

in Algorithm on 구현

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

풀이

구현 문제 였다. 이전 칸과 비교하여 체크해주는 문제.

높이가 이전과 같다면 지나갈 수 있고, 1 차이나면 경사로를 설치해야 한다.

경사로의 높이는 1로, 길이는 L로 고정되어 있어서 이전 칸과 1 차이날 때,

L길이의 for문을 통해 경사로를 놓을 수 있는지 탐색했다.

경사로의 바닥면의 높이가 다 같은지, 이미 설치된 경사로가 없는지 체크해 주었다.

이차원배열의 행과 열을 모두 체크해야 했다.

함수를 재사용 하기 위해 탐색할 부분을 일차원배열로 만들어 하나의 함수를 이용했다.

메모리: 15048KB

시간: 144ms

언어: Java 11

코드

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

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

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

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

        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans += makeRoad(i);
        }

        System.out.println(ans);
    }

    private static int makeRoad(int num) {
        int result = 0;

        if (check(board[num])) {
            result++;
        }

        int[] tmp = new int[N];
        for (int i = 0; i < N; i++) {
            tmp[i] = board[i][num];
        }
        if (check(tmp)) {
            result++;
        }

        return result;
    }

    private static boolean check(int[] arr) {
        boolean[] visit = new boolean[N];

        for (int i = 1; i < N; i++) {
            if (arr[i] == arr[i - 1]) {
                continue;
            } 
            // 이전 칸보다 1 높다면 경사로 놓을 수 있는지 검사
            else if (arr[i] == arr[i - 1] - 1) {
                for (int j = 0; j < L; j++) {
                    if (i + j >= N) {
                        return false;
                    }
                    if (arr[i] != arr[i + j]) {
                        return false;
                    }
                    visit[i + j] = true;
                }
            } 
            // 이전 칸보다 1 낮다면 경사로 놓을 수 있는지 검사
            else if (arr[i] == arr[i - 1] + 1) {
                for (int j = 1; j <= L; j++) {
                    if (i - j < 0 || visit[i - j]) {
                        return false;
                    }
                    if (arr[i - 1] != arr[i - j]) {
                        return false;
                    }
                    visit[i - j] = true;
                }
            } 
            // 이전 칸과 1 이상 차이나면 불가능
            else {
                return false;
            }
        }

        return true;
    }

}