백준 14890번(Java) 경사로

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

14890번: 경사로

 

구현 문제입니다.

2차원 배열에서 지나갈 수 있는 길이 몇개인지를 판별하는 문제인데, 지나갈 수 있는 길에 대한 조건을 잘 코딩하는 것이 중요했습니다.

 

지나갈 수 있는 길은 한 열, 또는 한 행만을 판단합니다. 따라서, 전체 배열은 2차원 배열이지만, 체크하는 함수를 따로 분리해서, 1차원 배열을 받아 체크하면 될 것이라고 생각했습니다.

 

문제의 조건에 나와있듯이, 길의 높이가 모두 같으면 그 길은 통과 가능합니다. 만약 높이가 같지 않다면 경사로를 놓을 수 있는가를 판단해야합니다. 따라서, 높이가 모두 같은지를 체크 후에 경사로 설치가 가능한지를 판단해야합니다.

 

이 경사로 설치 가능 여부를 코딩하는 것이 조금 복잡한데, 높이 차이가 1인지, 길의 범위를 벗어나지는 않는지, 이미 경사로가 놓여있지는 않은지 확인해야합니다. 또, 높이가 높은 쪽과 낮은 쪽의 방향을 구별해야합니다.

 

예외 처리에 대한 부분이 조금 까다롭지만, 별다른 알고리즘이나 자료구조를 필요로 하지 않는 문제였습니다.

구현 문제는 풀다보면 얼마나 예외처리를 잘할 수 있는지가 중요하고, if, for, while 등의 가장 기초적이고 필수적인 제어문을 잘 다루는 것이 중요하다고 생각이 들었습니다.

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = 0;

        int n = scanner.nextInt();
        int l = scanner.nextInt();
        int[][] map = new int[n][n];

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                map[i][j] = scanner.nextInt();
            }
        }

        for (int i=0; i<n; i++) {
            ArrayList<Integer> colList = new ArrayList<>();
            ArrayList<Integer> rowList = new ArrayList<>();
            int[] cols = new int[n];
            int[] rows = new int[n];

            for (int j=0; j<n; j++) {
                colList.add(map[i][j]);
                rowList.add(map[j][i]);
            }

            for (int z=0; z<colList.size(); z++) {
                cols[z] = colList.get(z);
                rows[z] = rowList.get(z);
            }

            if (checkRoad(cols, l)) {
                count++;
            }

            if (checkRoad(rows, l)) {
                count++;
            }
        }

        System.out.println(count);
    }

    public static boolean checkRoad(int[] road, int l) {
        boolean isSameHeight = true;

        for (int i=0; i<road.length-1; i++) {
            if (road[i] != road[i+1]) {
                isSameHeight = false;
                break;
            }
        }

        if (isSameHeight) {
            return true;
        }

        boolean[] already = new boolean[road.length];

        for (int i=0; i<road.length-1; i++) {
            if (road[i] != road[i+1]) {
                if (Math.abs(road[i] - road[i+1]) != 1) {
                    return false;
                }

                int count = 0;

                if (road[i] > road[i+1]) {
                    int height = road[i+1];

                    while (count < l) {
                        if ((i+1+count) >= road.length || road[i+1+count] != height || already[i+1+count]) {
                            return false;
                        }

                        already[i+1+count] = true;
                        count++;
                    }
                } else {
                    int height = road[i];

                    while (count < l) {
                        if ((i-count) < 0 || road[i-count] != height || already[i-count]) {
                            return false;
                        }

                        already[i-count] = true;
                        count++;
                    }
                }
            }
        }
        return true;
    }
}