위에서 정리한 조건에 부합하게 경사로를 설치해서
각 행과 열에 대해서 하나씩 지날 수 있는 길인지 체크해서 카운팅하는 문제입니다.
문제는 경사로 설치 구현이겠죠.
제가 구현한 방식은 이렇습니다.
// 경사로를 설치할 수 있는지 체크하고,
// 설치할 수 있다면 설치하고 true 리턴
// 설치할 수 없다면 false 리턴
static boolean isFit(int y, int x, int dir) {
// 이미 설치돼있을 때
if (fit[y][x]) return false;
// 원본 좌표 저장
int oriY = y;
int oriX = x;
// 이전 좌표의 높이
int prev = M[y][x];
// 경사로의 길이만큼 체크
for (int i = 0; i < L - 1; i++) {
y += my[dir];
x += mx[dir];
// 도로를 벗어났을 때
if (y < 0 || y >= N || x < 0 || x >= N) return false;
// 이전 좌표의 높이와 현재 좌표의 높이가 다를 때
if (prev != M[y][x]) return false;
// 이미 설치했을 때
if (fit[y][x]) return false;
// 이전 좌표의 높이 갱신
prev = M[y][x];
}
// 설치할 수 있다면 경사로를 설치
y = oriY;
x = oriX;
fit[y][x] = true;
for (int i = 0; i < L - 1; i++) {
y += my[dir];
x += mx[dir];
fit[y][x] = true;
}
return true;
}
설치할 좌표와 설치할 방향을 인자로 받아서 설치할 수 있는지 체크하고
설치가 가능하면 설치를 하는 함수입니다.
이 함수를 각 행과 열을 체크할 때 호출함으로서 지날 수 있는 도로인지 판별할 수 있습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N, L, M[][], my[] = {-1, 0, 1, 0}, mx[] = {0, 1, 0, -1};
static boolean[][] fit;
// 경사로를 설치할 수 있는지 체크하고,
// 설치할 수 있다면 설치하고 true 리턴
// 설치할 수 없다면 false 리턴
static boolean isFit(int y, int x, int dir) {
// 이미 설치돼있을 때
if (fit[y][x]) return false;
// 원본 좌표 저장
int oriY = y;
int oriX = x;
// 이전 좌표의 높이
int prev = M[y][x];
// 경사로의 길이만큼 체크
for (int i = 0; i < L - 1; i++) {
y += my[dir];
x += mx[dir];
// 도로를 벗어났을 때
if (y < 0 || y >= N || x < 0 || x >= N) return false;
// 이전 좌표의 높이와 현재 좌표의 높이가 다를 때
if (prev != M[y][x]) return false;
// 이미 설치했을 때
if (fit[y][x]) return false;
// 이전 좌표의 높이 갱신
prev = M[y][x];
}
// 설치할 수 있다면 경사로를 설치
y = oriY;
x = oriX;
fit[y][x] = true;
for (int i = 0; i < L - 1; i++) {
y += my[dir];
x += mx[dir];
fit[y][x] = true;
}
return true;
}
public static void main(String[] args) throws Exception {
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0]);
L = Integer.parseInt(s[1]);
M = new int[N][N];
fit= new boolean[N][N];
int r, c, cnt = 0;
for (r = 0; r < N; r++) {
s = br.readLine().split(" ");
for (c = 0; c < N; c++)
M[r][c] = Integer.parseInt(s[c]);
}
// 행 검사
out:
for (r = 0; r < N; r++) {
int prev = M[r][0];
for (c = 1; c < N; c++) {
int cur = M[r][c];
// 이전 좌표의 높이와 현재 좌표의 높이의 차이가 1보다 클 때
if (Math.abs(cur - prev) > 1) continue out;
// 현재 좌표가 이전 좌표보다 1크고 이전 좌표로부터 서쪽으로 경사로 설치가 불가능할 때
if (cur > prev && !isFit(r, c - 1, 3)) continue out;
// 현재 좌표가 이전 좌표보다 1작고 현재 좌표로부터 동쪽으로 경사로 설치가 불가능할 때
if (cur < prev && !isFit(r, c, 1)) continue out;
prev = cur;
}
cnt++;
}
// 설치했던 경사로 모두 제거
for (r = 0; r < N; r++)
for (c = 0; c < N; c++)
fit[r][c] = false;
// 열 검사
out:
for(c = 0; c < N; c++) {
int prev = M[0][c];
for (r = 1; r < N; r++) {
int cur = M[r][c];
// 이전 좌표의 높이와 현재 좌표의 높이의 차이가 1보다 클 때
if (Math.abs(cur - prev) > 1) continue out;
// 현재 좌표가 이전 좌표보다 1크고 이전 좌표로부터 북쪽으로 경사로 설치가 불가능할 때
if (cur > prev && !isFit(r - 1, c, 0)) continue out;
// 현재 좌표가 이전 좌표보다 1작고 현재 좌표로부터 남쪽으로 경사로 설치가 불가능할 때
if (cur < prev && !isFit(r, c, 2)) continue out;
prev = cur;
}
cnt++;
}
bw.write(cnt + "");
bw.close();
}
}