白駿14890号:スロープロード
28636 ワード
問題の説明
方法
pseudocode
Main(){
모든 행 배열과 열 배열에 대해 SlideCheck를 진행.
}
SlideCheck(배열){
for(i=0부터N-1까지){
if(i번째 값과 i+1번째 값이 2 이상 차이나면) return false
if(i번쨰 칸에 올라가는 경사로와 내려가는 경사로를 모두 놓아야 하는 상황이면) return false
if(i번째 값보다 i+1번째 값이 1 크면){ // 올라가는 경사로가 필요하면
if(!UpSlideCheck) return false // 올라가는 경사로를 못놓으면 false
올라가는 경사로를 놓을 수 있으면 해당 칸들을 중복사용 못하게 방문처리
}
if(i번째 값보다 i+1번쨰 값이 1 작으면){ // 내려가는 경사로가 필요하면
if(!DownSlideCheck) return false // 내려가는 경사로를 못놓으면 false
}
}
return true //못놓는 경우를 모두 피해갔으면 해당 배열은 길로 지나갈 수 있음.
}
UpSlideCheck(){
if(놓아야 하는 곳이 배열 밖이면) return false;
for(now를 포함한 왼쪽 L개의 블록을 검사하면서){
if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
}
}
DownSlideCheck(){
if(놓아야 하는 곳이 배열 밖이면) return false;
for(now를 포함한 오른쪽 L개의 블록을 검사하면서){
if(now블록과 숫자가 다르거나, 해당칸에 이미 블록이 놓여있으면) return false
}
}
正解
import java.util.*;
public class Main {
static int N, L, Score;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
L = sc.nextInt();
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = sc.nextInt();
}
}
for (int i = 0; i < N; i++) {
//열 배열을 구합니다
int[] colArr = new int[N];
for (int j = 0; j < N; j++) {
colArr[j] = board[j][i];
}
// 행 배열 길을 건널 수 있는지 체크합니다.
if (SlideCheck(board[i]))
Score++;
// 열 배열 길을 건널 수 있는지 체크합니다.
if (SlideCheck(colArr))
Score++;
}
System.out.println(Score);
}
public static boolean SlideCheck(int[] arr) {
boolean[] v = new boolean[N];
// 해당 칸(i)과 다음 칸(i+1)의 값이 다른지 비교합니다.
for (int i = 0; i < N - 1; i++) {
// 2칸 이상 차이가 나면 길을 건널 수 없습니다.
if (Math.abs(arr[i] - arr[i + 1]) >= 2)
return false;
// 내려가는 경사로와 올라가는 경사로를 동시에 요구하는 길은 결국 건널 수 없는 길입니다.
if ((i < N && arr[i] < arr[i + 1] && UpSlideCheck(arr, i, v))
&& (i > 0 && arr[i - 1] > arr[i] && DownSlideCheck(arr, i + 1, v))) {
return false;
}
// 올라가는 경사로가 필요합니다.
if (arr[i] < arr[i + 1]) {
// 올라가는 경사로를 설치할 수 없다면 false를 반환합니다.
if (!UpSlideCheck(arr, i, v))
return false;
// 올라가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
for (int j = i - L + 1; j <= i; j++) {
v[j] = true;
}
}
// 내려가는 경사로가 필요합니다.
if (arr[i] > arr[i + 1]) {
// 내려가는 경사로를 설치할 수 없다면 false를 반환합니다.
if (!DownSlideCheck(arr, i + 1, v))
return false;
// 내려가는 경사로를 설치했다면 해당 칸들에는 더 이상 경사로를 설치할 수 없습니다.
for (int j = i + 1; j <= i + 1 + L - 1; j++) {
v[j] = true;
}
}
}
return true;
}
public static boolean UpSlideCheck(int[] arr, int now, boolean[] v) {
// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
if (now - L + 1 < 0)
return false;
// now를 포함한 왼쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
int Std = arr[now];
for (int i = now - L + 1; i < now; i++) {
if ((arr[i] != Std) || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
return false;
}
return true;
}
public static boolean DownSlideCheck(int[] arr, int now, boolean[] v) {
// 배열의 범위를 벗어나면 경사로를 놓을 수 없습니다.
if (now + L - 1 >= N)
return false;
// now를 포함한 오른쪽 L개의 블록이 모두 같은 값인지를 판단합니다.
int Std = arr[now];
for (int i = now; i <= now + L - 1; i++) {
if (arr[i] != Std || v[i]) //블록값이 다르거나 해당칸에 이미 경사로를 놓았다면 길을 건널 수 없습니다.
return false;
}
return true;
}
}
Reference
この問題について(白駿14890号:スロープロード), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-14890번-경사로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol