https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH&categoryId=AWIeW7FakkUDFAVH&categoryType=CODE&problemTitle=4014&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

활주로 건설

풀이

행과 열을 읽어 행 또는 열이 활주로가 가능하다면 cnt를 증가시키면 된다.

• 모든 행과 열에 대해서 현재 행 또는 열이 활주로 건설이 가능한지 검사한다.
• 만약 건설이 가능하면 cnt를 증가시킨다.
• 가능하지 안핟면 경사로를 설치해서 활주로 건설이 가능한지 검사한다.
• 경사로를 설치할 때는 두가지 경우가 있다.
  • 지대가 1 높아지는 경우
  • 지대가 1 낮아지는 경우

위 사항만 고려하면 정답을 찾을 수 있다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, x;
    static int[][] board;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] line;
        int T = Integer.parseInt(br.readLine().trim());
        for (int t = 0; t < T; t++) {
            line = br.readLine().split(" ");
            n = Integer.parseInt(line[0]);
            x = Integer.parseInt(line[1]);

            board = new int[n][n];

            for (int i = 0; i < n; i++) {
                line = br.readLine().split(" ");
                board[i] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
            }
            int ans = 0;
            // 행 활주로 검사
            for (int i = 0; i < n; i++) {
                // 절벽이 없다.
                if (isRowPossible(i)) {
                    ans++;
                }
                // 경사로 설치 가능 검사
                else {
                    if (canRowBuild(i)) {
                        ans++;
                    }
                }
            }
            for(int j = 0; j<n;j++) {
                if(isColPossible(j))
                    ans++;
                else {
                    if(canColBuild(j))
                        ans++;
                }
            }
            bw.write("#" + (t + 1) + " " + ans + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean isRowPossible(int i) {
        int s = board[i][0];
        for (int j = 1; j < n; j++) {
            if (board[i][j] != s)
                return false;
        }
        return true;
    }

    private static boolean canRowBuild(int i) {
        // 경사로 설치 여부를 저장
        boolean[] built = new boolean[n];
        int cnt = 0;
        int prev = board[i][0];

        for (int j = 0; j < n; j++) {
            int cur = board[i][j];
            if (cur == prev) {
                cnt++;
            } else {
                if (cur == prev + 1) {
                    if (cnt >= x) {
                        for (int k = j - x; k < j; k++) {
                            // 이미 지어진 경사로에는 경사로를 설치 불가
                            if (built[k])
                                return false;
                            built[k] = true;
                        }
                        cnt = 1;
                    } else
                        return false;
                } else if (cur == prev - 1) {
                    if (j + x - 1 < n) {
                        for (int k = j; k < j + x; k++) {
                            if (built[k] || board[i][k] != cur)
                                return false;
                            built[k] = true;
                        }
                        cnt = 0;
                        j = j + x - 1;
                    } else
                        return false;
                }
                else
                    return false;
                prev = cur;
            }
        }
        return true;
    }

    private static boolean isColPossible(int j) {
        int s = board[0][j];
        for (int i = 1; i < n; i++) {
            if (board[i][j] != s)
                return false;
        }
        return true;
    }

    private static boolean canColBuild(int j) {
        boolean[] built = new boolean[n];
        int cnt = 0;
        int prev = board[0][j];
        for (int i = 0; i < n; i++) {
            int cur = board[i][j];
            if (cur == prev) {
                cnt++;
            } else {
                if (cur == prev + 1) {
                    if (cnt >= x) {
                        for (int k = i - x; k < i; k++) {
                            // 이미 지어진 경사로에는 경사로를 설치 불가
                            if (built[k])
                                return false;
                            built[k] = true;
                        }
                        // 한칸 위로 이동
                        cnt = 1;
                    } else
                        return false;
                } else if (cur == prev - 1) {
                    if (i + x - 1 < n) {
                        for (int k = i; k < i + x; k++) {
                            if (built[k] || board[k][j] != cur)
                                return false;
                            built[k] = true;
                        }
                        cnt = 0;
                        i = i + x - 1;
                    } else
                        return false;
                }
                else
                    return false;
                prev = cur;
            }
        }
        return true;
    }
}