[백준] 14890번: 경사로 - java

문제

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

14890번: 경사로

 

접근법

각 행과 열 마다 경사로를 설치할 수 있는지 확인하면 된다. 경사로를 설치할 수 있는 조건을 간단히 정리하면 높이의 차가 1인 곳에서 낮은 곳에 L만큼 설치할 수 있는 칸이 존재하면 된다.

 

나는 (r, c)에서 direction(수평 or 수직) 방향으로 경사로를 설치할 수 있으면 true, 아니면 false를 반환하는 함수를 만들었다. -> 가독성이 안 좋고 어차피 (0, i)와 (i, 0)에서 검사를 시작하도록 고정되어 있기 때문에 모든 행을 검사하는 함수, 모든 열을 검사하는 함수로 나누어 작성했다.

 

수평 또는 수직 방향으로 for 문을 계속 돌면서 이동하다가 높이의 차가 발생하는 경우 경사로를 설치할 수 있는지 검사했는데, 설치할 수 없는 경우 바로 false를 반환하도록 했다. 설치할 수 없는 조건을 정리하면 아래와 같다. 1번은 쉽게 구현할 수 있지만, 2번과 3번은 약간의 고민이 필요했다.

1. 높이의 차가 1이 아닌 경우
2. 연속된 낮은 칸의 길이가 L보다 작은 경우
3. 연속된 낮은 칸의 길이가 L보다는 크지만, 이미 경사로가 설치된 경우

 

낮은 칸의 길이 구하기

우리는 낮은 칸에 경사로를 설치해야 하기 때문에 높이의 차가 1인 구간을 발견하면 낮은 칸이 최대 몇 칸 존재하는지 알아야 한다.

예를 들어 이러한 구간이 있다고 할 때, 낮은 칸의 길이는 2이다. 경사로의 길이도 2이기 때문에 경사로를 설치할 수 있다. 하지만 높이의 차가 1인 구간을 발견할 때마다 반복문을 돌며 낮은 칸의 길이를 계산하는 것은 비효율적이라고 생각해서 각 구간의 길이를 저장하는 배열을 만들었다. 

각 구간의 길이란 같은 높이로 연속된 구역을 말한다. 주의할 점은 수평과 수직 관점에서 볼때 구간의 길이가 달라지기 때문에 나는 2개의 배열을 만들어서 따로 저장해주었다. 그리고 우리가 검사를 하는 경우는 높이의 차가 발생하는 경계선이기 때문에 경계선에만 값을 저장해도 무방하다.

 

수평과 수직 기준에서 각 구역의 길이를 경계선에만 저장한 경우 배열의 상태는 아래와 같다.

 

이제 낮은 칸의 길이는 먼저 지도에서 낮은 구간이 왼쪽인지 오른쪽인지 알아낸 뒤, 저장해 둔 구간의 값을 가지고 L보다 작은 경우는 설치할 수 없다고 판단하면 된다.

 

경사로를 이미 설치한 경우

경사로를 설치할 때마다 저장을 해두어야 하므로 각 행과 열을 검사할 때마다 boolean 배열을 사용해 설치한 경사로들을 저장해주었다. 여기서 주의할 점은 경사로를 왼쪽에 설치하는 경우 인덱스를 줄이면서 검사하고, 오른쪽에 설치하는 경우 인덱스를 늘리며 검사해야 한다는 것이다.

 

코드가 조금 복잡해져서 경사로 설치 여부를 저장하는 boolean 배열을 static으로 빼준 뒤, 경사로 설치하는 함수를 따로 작성해 설치할 수 없는 경우는 false를 반환하도록 하였다.

 

코드

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

public class Main {

    static int N, L;
    static int[][] map;
    static int[][] horizontal;
    static int[][] vertical;
    static boolean[] installed;
    static int answer = 0;

    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];
        horizontal = new int[N][N];
        vertical = new int[N][N];

        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        initCountArr();

        for (int i = 0; i < N; i++) {
            if (horizontalPass(i)) {
                answer++;
            }
            if (verticalPass(i)) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    // 높이가 같은 칸의 개수를 수평, 수직 방향으로 저장한다
    private static void initCountArr() {
        for (int r = 0; r < N; r++) {
            Point start = new Point(r, 0);
            int count = 1;

            for (int c = 1; c < N; c++) {
                if (map[r][c] != map[r][c - 1]) {
                    horizontal[r][start.c] = horizontal[r][c - 1] = count;
                    start = new Point(r, c);
                    count = 1;
                } else {
                    count++;
                }
            }

            horizontal[r][start.c] = horizontal[r][N - 1] = count;
        }

        for (int c = 0; c < N; c++) {
            Point start = new Point(0, c);
            int count = 1;

            for (int r = 1; r < N; r++) {
                if (map[r][c] != map[r - 1][c]) {
                    vertical[start.r][c] = vertical[r - 1][c] = count;
                    start = new Point(r, c);
                    count = 1;
                } else {
                    count++;
                }
            }

            vertical[start.r][c] = vertical[N - 1][c] = count;
        }
    }

    // i번째 행의 경사로 설치 가능 여부 반환
    private static boolean horizontalPass(int i) {
        installed = new boolean[N];

        for (int j = 1; j < N; j++) {
            if (map[i][j - 1] != map[i][j]) {
                // 1. 높이 차가 1이 아닌 경우
                if (Math.abs(map[i][j - 1] - map[i][j]) != 1) {
                    return false;
                }

                int min = (map[i][j - 1] < map[i][j]) ? (j - 1) : j; // 낮은 칸의 열 번호
                boolean left = map[i][j - 1] < map[i][j];

                // 2. 경사로를 설치할 칸이 부족한 병우
                if (horizontal[i][min] < L) {
                    return false;
                }

                boolean possible = installSlope(min, left);
                // 3. 이미 경사로가 설치된 경우
                if (!possible) {
                    return false;
                }
            }
        }

        return true;
    }
    // i번째 열의 경사로 설치 가능 여부 반환
    private static boolean verticalPass(int i) {
        installed = new boolean[N];

        for (int j = 1; j < N; j++) {
            if (map[j - 1][i] != map[j][i]) {
                // 1. 높이 차가 1이 아닌 경우
                if (Math.abs(map[j - 1][i] - map[j][i]) != 1) {
                    return false;
                }

                int min = (map[j - 1][i] < map[j][i]) ? (j - 1) : j; // 낮은 칸의 열 번호
                boolean left = map[j - 1][i] < map[j][i];

                // 2. 경사로를 설치할 칸이 부족한 병우
                if (vertical[min][i] < L) {
                    return false;
                }

                boolean possible = installSlope(min, left);
                // 3. 이미 경사로가 설치된 경우
                if (!possible) {
                    return false;
                }
            }
        }

        return true;
    }

    // i에서 L만큼 경사로 설치, 불가능한 경우 false 반환
    private static boolean installSlope(int i, boolean left) {
        if (left) {
            for (int j = i; j > (i - L); j--) {
                if (installed[j]) {
                    return false;
                }
                installed[j] = true;
            }
        } else {
            for (int j = i; j < (i + L); j++) {
                if (installed[j]) {
                    return false;
                }
                installed[j] = true;
            }
        }

        return true;
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

코드가 지저분해서 조금 고쳐봐야 될 것 같다.. 중복되는 연산이 많아서 조금 더 고칠 수 있지 않을까 싶다.

 

주의할 점

처음에 설계를 꼼꼼히 했다면 오래 걸리지 않았을 문제였는데 생각보다 너무 오래 걸렸다. 왼쪽: 인덱스 감소 / 오른쪽: 인덱스 증가 까먹지 말자!