[Algorithm] SW 기출문제 - 경사로(14890) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 경사로 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/14890

14890번: 경사로

 

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = parseInt(st.nextToken());
        int L = parseInt(st.nextToken());

        PathMap path = new PathMap(N, L);

        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                path.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        System.out.println(path.calculatePossiblePath());
    }
}

class PathMap {
    int n; // n개
    int len; // 경사로 길이
    int[][] mapR; // 행 * 열
    int[][] mapC; // 열 * 행

    PathMap (int n, int len) {
        this.n = n;
        this.len = len;
        mapR = new int[n][n];
        mapC = new int[n][n];
    }

    void setMap(int row, int col, int value) {
        mapR[row][col] = value;
        mapC[col][row] = value;
    }

    int calculatePossiblePath() {
        int possiblePath = 0; // 최종 답

        for (int row = 0; row < n; row++) {
            if (isPossiblePath(mapR[row])) possiblePath++;
            if (isPossiblePath(mapC[row])) possiblePath++;
        }

        return possiblePath;
    }

    boolean isPossiblePath(int[] map) {
        int preH = map[0]; // 기준이 되는 높이
        int cnt = 1; // 경사로를 놓을 수 있는 길이 (초기화 1)

        for (int col = 1; col < n; col++) {
            if (preH == map[col]) cnt++; // 높이가 같다면 cnt 증가 (혹시 더 높은 높이가 나타나면 cnt로 판별)

            else if (preH + 1 == map[col]) { // 만약 이전보다 크다면
                if (cnt < len) return false; // 경사로를 놓을 수 있는 길이보다 짧다면
                preH++; // 기준점 업데이트 (높이 한칸 더 높게)
                cnt = 1; // 길이 초기화 (기준점은 아직 사다리를 안놓았으므로)
            }

            else if (preH - 1 == map[col]){ // 이전 높이가 더 크다면

                int nowCnt = 1;
                int nowH = map[col]; // 현재 높이를 기준으로 len개까지 같은 높이가 나와야 함

                for (int k = col + 1; k < n; k++) { // 다음 행 부터 개수 세기
                    if (nowH != map[k]) break; // 현재 높이와 같지 않은 경우
                    nowCnt++;
                    if (nowCnt >= len) break; // 경사로를 놓을 수 있는 길이 이상이 되면
                }
                if (nowCnt < len) return false; // 이보다 적은 경우 종료

                col += (len - 1); // col을 포함한 열부터 경사로를 놓으므로
                cnt = 0; // 새로 시작하는 지점은 이미 경사로가 놓여있으므로
                preH = nowH;
            }

            else return false;
        }
        return true;
    }
}

 

 

2. 풀이 중점 사항

 

처음에 문제를 접근할 때, 경사로를 놓게 되면 계속 유지되는 것이라고 판단하여 많은 시간을 소모하였습니다.

이후 문제를 다시 읽고 가능한 예시를 자세하게 보니 가능한 경우의 수 이므로 한 행 혹은 한 열 단위로 경사로를 놓을 수 있고,

놓은 사다리는 다른 행, 열에 영향을 주지 않는 것이었습니다. 따라서, visited와 같은 체크 변수는 필요하지 않았습니다. 

 

중요한 사항은 경사로를 설정하는 과정에서 이전 높이가 더 큰지 혹은 더 작은지, 같은지에 따라 다르게 분기를 처리해야 했습니다.

 

가능한 경우는 

• 이전 높이와 같음
• 이전 높이보다 1 큼
• 이전 높이보다 1 작음
• 그 외 모두 불가

 

이전 높이와 같음

이전 높이와 같다면, cnt++를 하여 혹여 이전 높이보다 1 크게 되는 상황에 대비해야 합니다.

 

이전 높이보다 1 큼

예를 들어 len = 3이고 높이가 3 3 3 4 라면

이전 높이가 같은 것이 3개가 있고 (cnt = 3) len과 같으므로 경사로를 놓을 수 있음을 의미합니다. 

 

preH++; cnt = 1; 를 설정하는 것은 현재 높이가 4이므로 이전 높이가 3인 것보다 1 크므로 업데이트를 하는 과정입니다.

cnt = 1은 경사로가 놓인 위치는 3 3 3입니다. 한 칸 높은 곳은 경사로가 놓이지 않으므로  해당 위치는 경사로를 놓을 수 있는 유효한 칸이기 때문에 cnt++를 합니다.

 

이전 높이보다 1 작음

이전 높이보다 1이 작은 경우는, 현재 위치한 높이를 nowH로 설정하여

for 문으로 col을 nowH와 다를 때까지 이동하여야 합니다.

 

else if (preH - 1 == map[col]){ // 이전 높이가 더 크다면

    int nowCnt = 1;
    int nowH = map[col]; // 현재 높이를 기준으로 len개까지 같은 높이가 나와야 함

    for (int k = col + 1; k < n; k++) { // 다음 행 부터 개수 세기
        if (nowH != map[k]) break; // 현재 높이와 같지 않은 경우
        nowCnt++;
        if (nowCnt >= len) break; // 경사로를 놓을 수 있는 길이 이상이 되면
    }
    if (nowCnt < len) return false; // 이보다 적은 경우 종료

    col += (len - 1); // col을 포함한 열부터 경사로를 놓으므로
    cnt = 0; // 새로 시작하는 지점은 이미 경사로가 놓여있으므로
    preH = nowH;
}

 

여기서 nowCnt가 len 이상이 되면 break를 하여 더 이상 탐색되지 않도록 합니다.

col += (len - 1)을 하는 이유는 다음과 같습니다.

 

만약 len = 3이고, 인덱스는 0 1 2 3 이고, 해당 높이는 4 3 3 3입니다.

인덱스 1이 인덱스 0인 높이 4보다 1 작으므로 인덱스 3까지 탐색하였고

nowCnt == len 이여서 경사로를 놓았다고 가정하겠습니다.

 

이 경우 4 경 경 경 이 됩니다.

col은 기존에 인덱스 1이었고, 인덱스 3까지 경사로를 놓게 됩니다. 

이때, 기존 높이는 preH가 nowH로 업데이트하고 인덱스 3까지 경사로를 놓았으므로  인덱스 3은 더 이상 경사로를 

놓을 수 없으므로 0으로 cnt를 초기화하게 되는 것입니다.!

 

나머지 자세한 풀이는 주석화 하였습니다.

이상으로 경사로 자바 풀이를 마치도록 하겠습니다. 감사합니다.!