[백준 14890] 경사로 (JAVA)

문제

https://www.acmicpc.net/problem/14890

풀이

저는 스택을 이용하여 해결했습니다. 스택을 쌓으면서 peek를 통해 높이가 같으면 peek값을 count하고 다르면 다시 push 하는 방법으로 스택에 쌓고 하나씩 pop하면서 비교하였습니다.

L = 1, [3, 2, 1, 1, 2 ,3]

Stack = [(높이, 갯수), (3,1), (2,1), (1,2), (2,1), (3,1)]

1) pop(3,1)과 peek(2,1)을 비교하여 pop이 더 크므로 peek의 갯수를 -1합니다.

2) pop(2,0)과 peek(1,2)을 비교하여 pop이 더 크므로 peek의 갯수를 -1합니다.

3) pop(1,1)과 peek(2,1)을 비교하여 peek이 더 크므로 pop의 갯수가 1개 이상인지 확인합니다.

4) pop(2,1)과 peek(3,1)을 비교하여 peek이 더 크므로 pop의 갯수가 1개 이상인지 확인합니다.

5) Stack의 사이즈가 1이하이므로 갈 수 있는 길입니다. (1~4과정에서 문제가 있을 경우 갈 수 없는 경로)

코드

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 ans = 0;

        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());
            }
        }

        Stack row = new Stack(N);
        Stack column = new Stack(N);

        for (int i = 0; i < N; i++) {
            row.push(new Road(map[i][0], 1));
            column.push(new Road(map[0][i], 1));
            for (int j = 1; j < N; j++) {
                Road road = row.peek();
                if (road.height == map[i][j]) road.add();
                else row.push(new Road(map[i][j], 1));

                road = column.peek();
                if (road.height == map[j][i]) road.add();
                else column.push(new Road(map[j][i], 1));
            }

            if (check(row, L)) ans++;
            if (check(column, L)) ans++;

            row.clear();
            column.clear();
        }

        System.out.println(ans);
        br.close();
    }

    public static boolean check(Stack stack, int L) {
        while (stack.size() > 1) {
            Road first = stack.pop();
            Road second = stack.peek();

            if (first.height > second.height) {
                if (second.count < L || first.height - second.height > 1) {
                    return false;
                } else {
                    second.count -= L;
                }
            } else {
                if (first.count < L || second.height - first.height > 1) {
                    return false;
                }
            }
        }

        return true;
    }

    public static class Stack {
        Road[] arr;
        int index;

        public Stack(int size) {
            this.arr = new Road[size];
            this.index = 0;
        }

        public void push(Road road) {
            arr[index++] = road;
        }

        public Road pop() {
            return arr[--index];
        }

        public Road peek() {
            return arr[index - 1];
        }

        public void clear() {
            index = 0;
        }

        public int size() {
            return index;
        }
    }

    public static class Road {
        int height, count;

        public Road(int height, int count) {
            this.height = height;
            this.count = count;
        }

        public void add() { count++; }

    }
}