[백준온라인] 14890번 경사로

문제 : https://www.acmicpc.net/problem/14890

14890번: 경사로

문제 요약 : 지도에서 경사로를 사용해 지나갈 수 있는 길의 개수 출력

입력	출력
2 ≤ N(크기) ≤ 100 1 ≤ [N][N](높이) ≤ 10 1 ≤ L(경사로길이) ≤ N	경사로를 이용해 갈 수 있는 길의 개수

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16366827	cbkpar	14890	맞았습니다!!	14060KB	96ms	Java	1692B

import java.io.*;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,l,i,j;
		String str = "";
		str = br.readLine();
		String[] arr = str.split(" ");
		n = Integer.parseInt(arr[0]);
		l = Integer.parseInt(arr[1]);
		
		int[][] map = new int[n][n];
		for(i=0;i<n;i++) {
			str = br.readLine();
			arr = str.split(" ");
			for(j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
			}
		}
		
		int path = 0;
        //왼쪽 위에서 아래 순서로 왼쪽에서 오른쪽으로 갈 수 있는지 확인
		for(i=0;i<n;i++) {
			int p = 1; //0번은 검사할 필요 없기 때문에 1번부터 검사
			int q = map[i][0]; // 저장된 높이
			int r = 1; // 검사해온곳까지 경사로를 놓을 수 있는 길이
			while(p<n) {
				if(map[i][p]==q) { // 높이가 같다면
					p++; // 다음블럭 검사
					r++; // 경사로 놓을 수 있는 길이 1증가
					continue;
				}else if(map[i][p]==q+1) { //블럭이 현재까지 검사해온 블럭보다 1칸 높다면
					if(r<l) break; // 블럭을 놓을 수 없으면 종료
					q=map[i][p]; // 저장해온 블럭 높이 수정
					r=1; // 놓을 수 있는 경사로 길이 1로 수정
					p++; // 다음 블럭 검사
					continue;
				}else if(map[i][p]==q-1) { //블럭이 현재까지 검사해온 블럭보다 1칸 낮다면
					int tmppath=1; // 경사로를 놓을 수 있는지 확인 초기 1칸
					for(j=1;j<l;j++) {
						if(p+j>=n) break; // 지도 범위보다 초과하면 종료
						if(map[i][p]!=map[i][p+j]) break; //높이가 다르다면 종료
						if(map[i][p]==map[i][p+j]) tmppath++; // 높이가 같으면 1칸 증가
					}
					if(tmppath<l) break; // 경사로를 놓을 수 없다면 종료
					p+=l; //경사로를 놓은 후 l블럭 다음부터 검사
					q=map[i][p-1];
					r=0; // 내려왔기때문에 그자리에 블럭을 놓을 수 없어서 경사로 길이0으로 초기화
					continue;
				}
				break;
			}
			if(p==n) path++; // 끝까지 건너 왔다면 길을 1개 증가
		}
        //위 왼쪽에서 오른쪽 순서로 위에서 아래로 갈 수 있는지 확인
        for(i=0;i<n;i++) {
			int p = 1;
			int q = map[0][i];
			int r = 1;
			while(p<n) {
				if(map[p][i]==q) {
					p++;
					r++;
					continue;
				}else if(map[p][i]==q+1) {
					if(r<l) break;
					q=map[p][i];
					r=1;
					p++;
					continue;
				}else if(map[p][i]==q-1) {
					int tmppath=1;
					for(j=1;j<l;j++) {
						if(p+j>=n) break;
						if(map[p][i]!=map[p+j][i]) break;
						if(map[p][i]==map[p+j][i]) tmppath++;
					}
					if(tmppath<l) break;
					p+=l;
					q=map[p-1][i];
					r=0;
					continue;
				}
				break;
			}
			if(p==n) path++;
		}
		System.out.println(path); // 가능한 길의 개수 출력
	}
}