문제

N*N인 지도의 각 칸에는 해당 칸의 높이가 적혀져 있다. 같은 높이인 칸끼리는 지나갈 수 있지만, 높이가 다르면 지나갈 수 없다. 그래서 높이가 1이고 길이는 L인 경사로를 놓아서 지나갈 수 있도록 만들었을 때 건널 수 있는 행/열의 개수를 출력하면 되는 문제이다.

풀이

go() 함수로 해당 행 혹은 열을 지나갈 수 있는지 체크한다.

• 행, 열의 좌표를 관리하기 복잡할 것 같아 heigth[] 배열에 해당 행 혹은 열의 높이 전체를 저장한다.
• 높이가 동일한 경우는 continue
• 인접한 칸과의 높이차이가 1보다 크면 지나갈 수 없다. (경사로의 높이가 무조건 1) -> false 리턴
• 현재 칸과 다음 칸의 높이차가 1일 때는 두가지 케이스로 나눠서 처리
  • 현재 칸 높이 > 다음 칸 높이 ↘
  • 현재 칸 높이 < 다음 칸 높이 ↗
    이렇게 해주는 이유는, 첫 번째 경우는 상관없지만 두 번째 경우에 i번째보다 i+1번째의 높이가 높을 때 경사로의 길이를 L만큼 설치해야하니까 뒤의 칸들을 j--하면서 순회해야한다.

범위내에 블록이 있고, 방문하지 않았으며 높이가 일정하다면 방문처리 해줌

소스 코드

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

public class BOJ_14890 {
    static int[][] map;
    static int n;
    static int l;

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

        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 (go(i, 0, 0)) {
                count++;
            }

            if (go(0, i, 1)) {
                count++;
            }
        }
        System.out.println(count);
    }

    static boolean go(int x, int y, int dir) {
        boolean[] visited = new boolean[n];
        int[] height = new int[n];

        for (int i = 0; i < n; i++) {
            height[i] = (dir == 0) ? map[x][y + i] : map[x + i][y];
        }

        for (int i = 0; i < n - 1; i++) {
            if (height[i] == height[i + 1]) {
                continue;
            }

            if (Math.abs(height[i] - height[i + 1]) > 1) {
                return false;
            }

            if (height[i] - 1 == height[i + 1]) {
                for (int j = i + 1; j <= i + l; j++) {
                    if (j >= n || visited[j] || height[j] != height[i + 1]) {
                        return false;
                    }
                    visited[j] = true;
                }
            } else if (height[i] + 1 == height[i + 1]) {
                for (int j = i; j > i - l; j--) {
                    if (j < 0 || visited[j] || height[j] != height[i]) {
                        return false;
                    }
                    visited[j] = true;
                }
            }

        }
        return true;
    }
}