[백준 14890번][Java] 경사로 - 구현, 쉬운 듯 어려운 너

www.acmicpc.net/problem/14890

14890번: 경사로

 

이 문제도 꽤 까다로웠네요.

 

주의할 점은 경사로를 만들 수 있는지 체크할 때 올라가는 방향, 내려가는 방향 모두 체크해야 된다는 점입니다.

그리고 해당 블럭에 경사로가 이미 설치되어 있는지도 기록해줘야 합니다.

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, L;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader();
//        InputReader reader = new InputReader("testcase.txt");
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ret = solve();
        System.out.println(ret);
        
    }

    private static int solve() {
        int ret = 0;
        //행 검사
        for (int row = 0; row < N; row++) {
            if(isPassableRow(row)) ret++;
        }

        //열 검사
        for (int col = 0; col < N; col++) {
            if(isPassableCol(col)) ret++;
        }

        return ret;
    }

    private static boolean isPassableRow(int row) {
        boolean[] hasSlope = new boolean[N];
        for (int i = 0; i < N-1; i++) {
            if(map[row][i] == map[row][i+1]) continue;
            //올라가는 경사
            if(map[row][i+1] - map[row][i] == 1 && canBuildSlopeOnRow(row, i, -1, hasSlope)) {
                continue;
            }
            //내려가는 경사
            if(map[row][i] - map[row][i+1] == 1 && canBuildSlopeOnRow(row, i+1, 1, hasSlope)) {
                i = i+L-1;
                continue;
            }
            return false;
        }
        return true;
    }

    private static boolean isPassableCol(int col) {
        boolean[] hasSlope = new boolean[N];
        for (int i = 0; i < N-1; i++) {
            if(map[i][col] == map[i+1][col]) continue;
            //올라가는 경사
            if(map[i+1][col] - map[i][col] == 1 && canBuildSlopeOnCol(i, col, -1, hasSlope)) {
                continue;
            }
            //내려가는 경사
            if(map[i][col] - map[i+1][col] == 1 && canBuildSlopeOnCol(i+1, col, 1, hasSlope)) {
                i = i+L-1;
                continue;
            }
            return false;
        }
        return true;
    }

    private static boolean canBuildSlopeOnRow(int currentRow, int currentCol, int dc, boolean[] hasSlope) {
        int col = currentCol;
        int checkCount = L-1;

        if(hasSlope[col]) return false;
        while(checkCount > 0) {
            int nextCol = col + dc;
            if(!isRange(currentRow, nextCol)) return false;
            if(map[currentRow][col] == map[currentRow][nextCol] && !hasSlope[nextCol]) {
                checkCount--;
                col = nextCol;
                continue;
            }
            return false;
        }
        //빠져나왔다면 다리를 설치할 수 있는 경우다.
        int start = Math.min(currentCol, col);
        int limit = Math.max(currentCol, col);
        for (int i = start; i <= limit; i++) {
            hasSlope[i] = true;
        }
        return true;
    }


    private static boolean canBuildSlopeOnCol(int currentRow, int currentCol, int dr, boolean[] hasSlope) {
        int row = currentRow;
        int checkCount = L-1;

        if(hasSlope[row]) return false;
        while(checkCount > 0) {
            int nextRow = row + dr;
            if(!isRange(nextRow, currentCol)) return false;
            if(map[nextRow][currentCol] == map[row][currentCol] && !hasSlope[nextRow]) {
                checkCount--;
                row = nextRow;
                continue;
            }
            return false;
        }
        //빠져나왔다면 다리를 설치할 수 있는 경우다.

        int start = Math.min(currentRow, row);
        int limit = Math.max(currentRow, row);
        for (int i = start; i <= limit; i++) {
            hasSlope[i] = true;
        }
        return true;
    }

    private static boolean isRange(int r, int c) {
        if(r < 0 || r >= N || c < 0 || c >= N) return false;
        return true;
    }

}

class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}