[백준 14890] 경사로(Java)

문제 링크 : https://www.acmicpc.net/problem/14890

이 문제는 문제의 조건대로 하나하나 구현해나가면 쉽게 풀 수 있습니다.

이 문제의 핵심은 경사로를 놓는 경우의 수를 어떤 식으로 설정하는가입니다. 경사로는 크게

1. 현재 값보다 큰 수를 위한 경사로를 놓기
2. 현재 값보다 작은 수를 위한 경사로를 놓기

입니다. 각 경우는 처리 방법이 살짝 다릅니다.

우선 1번의 경우, 현재 값 이전에 지나온 길이 모두 같으며 길이가 L보다 크거나 같은 경우 경사로를 놓을 수 있습니다.

하지만 2번의 경우는 조금 복잡한데요, 우선 다음 값부터 L번째 값까지 모든 수가 서로 같은지를 비교해야 합니다. 그럼 경사로를 놓을 수 있기 때문에 해당 위치로 인덱스를 옮겨주시면 됩니다. 이 때 마지막 L번째 값보다 1 작은 수로 옮겨야 하는데, 해당 로직은 반복문 내에서 진행하기 때문에 반복문이 1 증가시키는 카운트를 고려하여 1 작은 수로 옮긴 후 반복문에서 1을 증가시켜 L번째 값으로 이동하도록 설정해야 합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N,L;
    static int res = 0;
    static int[][] reqH = new int[101][101];
    static int[][] reqV = new int[101][101];

    static void move(int[][] req){
        for(int i=0;i<N;i++){
            boolean canMove = true;
            int prevRoad = 1; // 현재 칸을 포함해야 하므로 1부터 시작

            for(int j=0;j<N-1;j++){
                // 현재 칸과 다음 칸의 차이 계산
                int prev = req[i][j];
                int curr = req[i][j+1];
                int diff = Math.abs(prev-curr);

                // 다음 칸과 차이가 0일 경우
                if(diff == 0){
                    // 지나온 칸의 수를 1씩 더함
                    prevRoad++;
                }

                // 다음 칸과 차이가 1일 경우
                else if(diff == 1){
                    // 다음 칸이 현재 값보다 더 클 경우
                    if(curr > prev){
                        // 지나온 칸의 수가 L과 같거나 클 경우 경사로 설치
                        if(prevRoad >= L){
                            // 지나온 칸의 수 1로 초기화
                            prevRoad = 1;
                        }
                        // L과 다를 경우 실패
                        else{
                            canMove = false;
                            break;
                        }
                    }

                    // 다음 칸이 현재 값보다 더 작을 경우
                    else{
                        // 다음 칸부터 L번째 칸까지 세서 값이 모두 똑같은지 확인
                        for(int idx=1;idx<=L;idx++){
                            // 만약 값이 다르다면 경사로를 세울 수 없어 실패
                            if(curr != req[i][j+idx]){
                                canMove = false;
                                break;
                            }
                        }

                        // 경사로를 세운 마지막으로 이동
                        j += L-1;
                        // 이전 길은 경사로이기 때문에 새로운 경사로를 추가할 수 없어 0으로 초기화
                        prevRoad = 0;
                    }
                }

                // 다음 칸과 차이가 2인 경우
                // 무조건 실패
                else if(diff >= 2){
                    canMove = false;
                    break;
                }
            }
            if(canMove){
                res++;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                // 가로 검증, 세로 검증용 맵 각각 만들기
                reqH[i][j] = Integer.parseInt(st.nextToken());
                reqV[j][i] = reqH[i][j];
            }
        }

        move(reqH);
        move(reqV);
        System.out.println(res);
    }
}