Q14890: 경사로

주소 : www.acmicpc.net/problem/14890

14890번: 경사로

쉽게 풀었던 문제인데, 오랜만에 알고리즘 공부하려니 빡세네요.

머리 좀 풀고 슬슬 시작하려합니다.

 

이 문제는 정답비율이 54%로 꽤 높은 편이네요.

다들 문제는 이해하셨을거라, 생각하고 시작하겠습니다.

 

사다리를 설치 조건은 다음과 같습니다.

사다리 설치가 불가능한 상황을 다음 케이스로 분류해볼게요

 

1번 : 이동 높이가 1보다 큰 경우

-> 현재 칸의 높이와 다음 칸의 높이의 차이를 계산해야겠네요.

 

2, 3, 4번 : 이미 사다리를 설치하여 겹쳐서 설치할 수 없는 경우

-> 사다리를 설치할 때마다 설치 체크를 해야겠네요.

 

기타 : 사다리 설치할 공간이 없어, 사다리를 설치할 수 없는 경우 (같은 높이의 공간이 사다리 길이보다 짧거나, 맵 밖으로 벗어나는 경우)

-> 사다리 설치 공간을 확인해야겠네요.

 

이제 코드를 볼까요?

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

public class Main {

    static int mapSize = 0;
    static int ladderSize = 0;
    static int[][] map = null;

    static int resultValue = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        mapSize = Integer.parseInt(st.nextToken());
        ladderSize = Integer.parseInt(st.nextToken());

        map = new int[mapSize][mapSize];
        for (int y = 0; y < mapSize; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < mapSize; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        for (int y = 0; y < mapSize; y++) { //가로 계단 한줄만 넘겨줘서 계산 
            doCalculate(map[y]);
        }

        for (int x = 0; x < mapSize; x++) {
            int[] singleMap = new int[mapSize];
            for (int y = 0; y < mapSize; y++) {
                singleMap[y] = map[y][x];
            }
            doCalculate(singleMap); //세로 계단 한줄만 넘겨줘서 계산 
        }

        System.out.println(resultValue);
}

    static void doCalculate(int[] heightMap) {
        boolean[] isUseLadder = new boolean[mapSize];

        for (int currentX = 0; currentX < mapSize; currentX++) {
            if (currentX + 1 >= mapSize) {
                continue;
            }

            int gapHeight = heightMap[currentX + 1] - heightMap[currentX]; 
            if (gapHeight == 0) { // 수평 이동일 때 
                continue;
            } else if (gapHeight == 1) { //한칸 올라 갈 때
                if (currentX - ladderSize + 1 < 0 ) { //사다리 설치 공간이 없으면 종료 
                    return;
                }

                for(int beforeX = currentX - ladderSize + 1; beforeX <= currentX; beforeX++) { //이전 계단 높이를 계산하여, 사다리 설치 가능 확인  
                    if (isUseLadder[beforeX] || heightMap[currentX] != heightMap[beforeX]) { //이미 사다리를 설치했거나, 설치 불가능 할 때 종료 
                        return;
                    }

                    isUseLadder[beforeX] = true; //사다리 설치 체크 
                }
            } else if (gapHeight == -1) { // 한칸 내려 갈 때
                if (currentX + ladderSize >= mapSize) { //사다리 설치 공간이 없으면 종료  
                    return;
                }

                for(int nextX = currentX + 1; nextX <= currentX + ladderSize; nextX++) { //다음 계단 높이를 계산하여, 사다리 설치 가능 확인 
                    if (isUseLadder[nextX] || heightMap[currentX + 1] != heightMap[nextX]) { //설치 불가능 할 때 종료 
                        return;
                    }

                    isUseLadder[nextX] = true; //사다리 설치 체크 
                }

                currentX = currentX + ladderSize - 1; //사다리 설치한 공간으로 이동 
            } else {
                return;
            }
        }

        resultValue += 1;
        }
}

 

코드가 너무 어질어질 하네요. (사실 이해는 할 수 있지만요.) "Clean Code" 서적의 내용을 떠올리며 이쁘게 다듬어볼게요. 

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

public class Main {

    static int mapSize = 0;
    static int ladderSize = 0;
    static int[][] map;
    static int resultValue = 0;
    static int[] heightMap;
    static boolean[] isUseLadder;

    public static void main(String[] args) throws Exception {

        inputDate();    //입력 받아 기본 구성
        searchHorizontal();    //가로로 된 길 찾기
        searchVertical();    //세로로 된 길 찾기

        System.out.println(resultValue);  //결과 출력
    }

    static void inputDate() throws Exception {    //입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        mapSize = Integer.parseInt(st.nextToken());
        ladderSize = Integer.parseInt(st.nextToken());

        map = new int[mapSize][mapSize];
        for (int y = 0; y < mapSize; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < mapSize; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
            }
        }
    }

    static void searchHorizontal() {    //가로 한 줄만 세팅하여 경로 찾기
        for (int y = 0; y < mapSize; y++) {
            heightMap = map[y];
            doWalk();
        }
    }

    static void searchVertical() {    //세로 한 줄만 세팅하여 경로 찾기
        for (int x = 0; x < mapSize; x++) {
            heightMap = new int[mapSize];
            for (int y = 0; y < mapSize; y++) {
                heightMap[y] = map[y][x];
            }
            doWalk();
        }
    }

    static void doWalk() {    //경로 찾기
        isUseLadder = new boolean[mapSize];    //사다리 설치 체크를 위한 어레이
        for (int currentX = 0; currentX < mapSize; currentX++) {
           if (currentX + 1 >= mapSize) {
                continue;
            }

            int gapHeight = heightMap[currentX + 1] - heightMap[currentX];   //현재 높이와 다음 칸의 높이 계산하기
            if (gapHeight == 0) { // 높이가 같은 경우
                continue;
           } else if (gapHeight == 1) { //한칸 올라 갈 경우
                if (getIsImpossibleUp(currentX)) {    //올라갈 수 없는지 확인하여, 올라갈 수 없으면 종료
                    return;
                }
            } else if (gapHeight == -1) { // 한칸 내려 갈 경우
                if (getIsImpossibleDown(currentX)) {    //내려갈 수 없는지 확인하여, 내려갈 수 없으면 종료
                    return;
                }
                currentX = currentX + ladderSize - 1; //사다리 설치한 공간으로 이동 
           } else {    //사다리 실패 1번 조건인 경우(높이가 1보다 큰 경우)
               return;
            }
        }

       resultValue += 1;
    }

    static boolean getIsImpossibleUp(int currentX) {
        if (currentX - ladderSize + 1 < 0 ) { //사다리 실패 '기타' 조건인 경우(설치 할 사다리가 맵을 뚫고 나갈 경우) 
            return true;
        }

        for(int beforeX = currentX - ladderSize + 1; beforeX <= currentX; beforeX++) { //이전 계단 높이를 계산하여, 사다리 설치 가능 확인  
            if (isUseLadder[beforeX] || heightMap[currentX] != heightMap[beforeX]) {  //사다리 실패 2,3,4번, '기타' 인 경우(이미 사다리를 설치했거나, 높이가 달라 사다리 설치 공간이 없음) 
                return true;
            }

            isUseLadder[beforeX] = true; //사다리 설치 체크 
        }
        return false;
    }

    static boolean getIsImpossibleDown(int currentX) {
        if (currentX + ladderSize >= mapSize) { //사다리 실패 '기타' 조건인 경우(설치 할 사다리가 맵을 뚫고 나갈 경우) 
            return true;
        }

        for(int nextX = currentX + 1; nextX <= currentX + ladderSize; nextX++) { //다음 계단 높이를 계산하여, 사다리 설치 가능 확인 
            if (isUseLadder[nextX] || heightMap[currentX + 1] != heightMap[nextX]) { //사다리 실패 2,3,4번, '기타' 인 경우(이미 사다리를 설치했거나, 높이가 달라 사다리 설치 공간이 없음) 
                return true;
            }

           isUseLadder[nextX] = true; //사다리 설치 체크 
        }
        return false;
    }
}

좀 보기 쉬워졌나요? 코드의 길이는 늘어났지만 가독성은 늘어났습니다.

숏코딩은 가독성이 떨어지죠. 로직도 로직이지만, 읽기 좋은 코드가 좋은 코드라 생각해요.

 

사다리 설치 불가능한 1, 2, 3, 4번과 기타 조건을 고려하여 코딩하면 되겠습니다.

 

피드백 감사합니다.