경사로

in Algorithm on 백준


백준 [14890] 경사로

문제보기
Alt text

풀이

입력과 동일한 지도와, 행과 열을 뒤바꾼 지도를 각각 탐색하여 행을 기준으로 탐색 진행. 현재 높이가 계속해서 동일한 길이를 가지고 있다가 높이가 한칸 더 높은 경우 바로 비교하여 사용했으며, 높이가 더 낮은 길을 마주쳤을 경우 동일한 길이가 얼마나 되는지 한번에 파악하여 경사로를 두고 이미 파악된 길이는 건너뛰어 탐색.

소스코드

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

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 = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[][] rowMap = new int[N][N];
        int[][] colMap = new int[N][N];

        // 지도 세팅
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                int val = Integer.parseInt(st.nextToken());
                rowMap[i][j] = val;
                colMap[j][i] = val;
            }
        }

        int result = 0;
        result += findRoute(N, L, rowMap);
        result += findRoute(N, L, colMap);

        System.out.println(result);
    }

    private static int findRoute(int N, int L, int[][] map) {
        int exitCnt = 0;

        for (int i = 0; i < N; i++) {
            int standardHeight = -1; // 기준 높이
            int sameHeightCnt = 0; // 현재 기준 높이가 연속된 횟수

            for (int j = 0; j < N; j++) {
                int crrntHeight = map[i][j];

                if (standardHeight < 0) { // 아직 기준 높이가 정해지지 않은 경우(시작점)
                    standardHeight = crrntHeight;
                    sameHeightCnt++;
                    continue;
                }

                if (Math.abs(standardHeight - crrntHeight) > 1) { // 연결된 루트의 높이가 1보다 큰 경우
                    break;
                }

                if (standardHeight == crrntHeight) {
                    sameHeightCnt++;
                } else {
                    if (standardHeight < crrntHeight) { // 현재 높이가 더 높은 경우, 이전 길에 경사로 설치
                        if (sameHeightCnt < L) { // 경사로를 설치할 길이가 안되는 경우
                            break;
                        } else {
                            sameHeightCnt = 1;
                        }
                    } else { // 현재 높이가 더 낮은 경우 앞으로의 경사로에 설치
                        int chkRoute = 1; // 현재 시작점 포함하여 1로 시작

                        for (int k = j + 1; k < N; k++) {
                            if (map[i][k] != crrntHeight) break;
                            chkRoute++;
                        }

                        if (chkRoute < L) { // 경사로를 설치할 수 없는 경우
                            break;
                        }

                        j += chkRoute - 1; // 현재와 동일한 길이까지 건너뛰기

                        sameHeightCnt = chkRoute - L; // 동일한 길이 중 경사로가 설치된 길은 제거
                    }

                    standardHeight = crrntHeight;
                }

                if (j >= N - 1) {
                    exitCnt++;
                }
            }
        }

        return exitCnt;
    }
}