알고리즘/문제풀이

[구현] 경사로문제

lipnus 2018. 10. 19. 23:42
반응형
package com.company;

import java.util.Scanner;

public class Runway {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N, L;
N = sc.nextInt();
L = sc.nextInt();

int[][] map = new int[N][N];

for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
map[i][j]=sc.nextInt();
}
}

int answerCount = 0;

//행검사
for(int i=0; i<N; i++){
if(lineCheck(map[i],L)) answerCount++;
}

//열검사
for(int i=0; i<N; i++){

int[] col = new int[N];
for(int j=0; j<N; j++){
col[j] = map[j][i];
}
if(lineCheck(col,L)) answerCount++;
}
System.out.println( answerCount );
}


static boolean lineCheck(int[] line, int L){

boolean[] covered = new boolean[line.length];

for(int i=0; i<line.length-1; i++){

//한칸 전진 가능
if(line[i]==line[i+1]) continue;
if(covered[i+1]) continue;

//1칸이상 차이나는 경사, 이길은 절대 못감
if( Math.abs(line[i]-line[i+1])>1 ) return false;

//한칸 앞 올라가는 경사(뒤쪽으로 놓음)
if(line[i]<line[i+1]){
int height = line[i];
if((i+1)-L < 0) return false; //경사판을 놓을 칸이 부족
for(int j=i; i-L<j; j--){
if(covered[j] || line[j]!=height) return false; //다른 경사판이 있어서 놓을 수가 없음
}
}

//한칸 앞 내려가는 경사
else if(line[i]>line[i+1]){

if(i+L >= line.length) return false; //경사판을 놓을 칸이 부족
int height = line[i+1];

for(int j=(i+1); j<i+1+L; j++){
if(line[j]==height){
covered[j]=true;
}else{
return false;
}
}
}

}
return true;
}
}


그냥.. 정신을 잘 집중해야 한다

반응형

'알고리즘 > 문제풀이' 카테고리의 다른 글

[조합(재귀), 완전탐색] 치킨배달  (0) 2018.10.20
[BFS] 탈주범 검거  (0) 2018.10.20
[BFS] 이상한 계산기  (0) 2018.10.18
단지번호 붙이기  (0) 2018.10.10
[BFS,DFS] 타겟넘버  (0) 2018.10.09