[백준 14890] 경사로 - JAVA

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

조건

• 지도의 한 행이나 열을 하나의 '길'로 정의
• 높이가 같을 경우 : 제약없이 지나갈 수 있음
• 높이가 다를 경우 : 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있음
  • 경사로는 높이 차이가 1이어야 하며, 길이가 $L$만큼 연속된 평지가 필요
  • 내리막길과 오르막길 모두 경사로를 놓을 수 있어야 함
  • 이미 경사로가 놓인 곳에 중복으로 놓을 수 없음

접근 방법

경사로는 항상 낮은곳에 설치됩니다.

따라서 다음과 같은 간단한 사고를 해야합니다.

• 높이가 1차이난다면
• 낮은 곳에 경사로를 설치할 수 있는지 판별

그러면 다음으로 해야될 것은

• 경사로가 왼쪽에 설치되는 경우
• 경사로가 오른쪽에 설치되는 경우

두 가지 방식에 대해서 고민해야 합니다.

왼쪽에 설치되는 경우는
지나오면서 stack 변수를 통해 설치 가능 여부를 판별할 수 있는 반면
오른쪽 설치는 아직 미확인된 칸이기 때문에 예측할 수 없습니다.

그렇기 떄문에 SuffixSameCount라는 배열을 사용했고
우측에서부터 순회해서 미리 해당칸의 연속성을 계산하고 저장했습니다.

이후부터는 간단합니다.

• 동일 높이면 카운트를 증가시킵니다.
• 오르막길을 만나면 현재까지 쌓인 카운트가 $L$ 이상인지 확인합니다.
• 내리막길을 만나면 suffixSameCount를 이용해 앞 공간을 확인하고, 경사로가 설치된 칸만큼 카운트를 음수$(-L + 1)$로 만들어 중복 설치를 방지했습니다.

이 문제에서는 같은 로직을 행과 열만 바꿔서 수행하기 때문에 두 개의 메서드로 나누지 않고
핵심 변수인 current next 등만 행, 열에 따라 변하도록 구현했습니다.

코드

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

public class Main {
    static StringTokenizer st;

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

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int count = 0;

        for (int i = 0; i < N; i++) {
            if (canBuildRoad(map, i, N, L, true)) count++;
            if (canBuildRoad(map, i, N, L, false)) count++;
        }

        System.out.println(count);
    }

    static boolean canBuildRoad(int[][] map, int pos, int N, int L, boolean isRow) {
        int[] suffixSameCount = new int[N];
        suffixSameCount[N - 1] = 1;

        int current = isRow ? map[pos][N-1] : map[N-1][pos];
        for (int i = N - 2; i >= 0; i--) {
            int nextHeight = isRow ? map[pos][i] : map[i][pos];
            if (current != nextHeight) {
                current = nextHeight;
                suffixSameCount[i] = 1;
            } else {
                suffixSameCount[i] = suffixSameCount[i + 1] + 1;
            }
        }

        current = isRow ? map[pos][0] : map[0][pos];
        int count = 1;

        for (int i = 1; i < N; i++) {
            int next = isRow ? map[pos][i] : map[i][pos];

            if (next == current) {
                count++;
            }
            else if (next == current - 1) {
                if (suffixSameCount[i] >= L) {
                    current = next;
                    count = -L + 1;
                } else {
                    return false;
                }
            }
            else if (next == current + 1) {
                if (count >= L) {
                    current = next;
                    count = 1;
                } else {
                    return false;
                }
            }
            else {
                return false;
            }
        }

        return true;
    }
}