[java]경사로 - 백준14890

문제

• 경사로(백준14890)

풀이

문제 해석을 하자면,

• 조건에 맞는 가능한 길의 개수를 구하라

풀이

• 총 2N개 길 탐색하므로 완전탐색으로 생각해도 충분
• 길이 성립하는지 판단하는 함수 구현이 중요하다 -> roadCheck 함수로 구현했다.
  • 이때, 하나의 길을 하나의 1차원 배열로 담아서 체크하는 식으로 했다.
  • 경사로 쌓을 때 -> 앞 L칸, 뒤 L칸 나눠서 확인
  • 332233 처럼 경사로 겹치는것도 판단 필수 -> visited 로 구현했다.

코드

public static int N, L, result;
public static int[][] inArr = new int [105][105];

public static void roadCheck(int[] road) {
    boolean check = true;
    boolean[] visited = new boolean[N+1]; // 경사로 겹침 판단에 사용 

    for(int i=0; i<N-1; i++) {
        if(road[i]==road[i+1]) continue; // 높이 동일
        else if(Math.abs(road[i]-road[i+1])!=1) { // 높이차이 1 아닐때
            check = false;
            break; 
        }
        // 이곳 부터는 높이 차이 1인 상황
        if(road[i] < road[i+1]) {
            for(int l=0; l<L; l++) { // "앞"의 L칸 확인
                if(i-l<0||i-l>=N || visited[i-l]) { // 범위체크 & 경사로 이미 사용한 부분인지 체크
                    check = false;
                    break;
                }
                if(road[i]!=road[i-l]) {
                    check = false;
                    break;
                }
                visited[i-l]=true;
            }
        }else { // road[i] > road[i+1]
            for(int l=0; l<L; l++) { // "뒤"의 L칸 확인
                if(i+1+l<0||i+1+l>=N || visited[i+1+l]) { // 범위체크
                    check = false;
                    break;
                }
                if(road[i+1]!=road[i+1+l]) {
                    check = false;
                    break;
                }
                visited[i+1+l]=true;
            }
        }

    }

    if(check) {
        result++;		
        // debug
        //			for(int i=0; i<N; i++) System.out.print(road[i]);
        //			System.out.println();
    }
}

public static void main(String[] args) throws Exception {
    //init
    //input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    L = Integer.parseInt(stk.nextToken());		
    for(int i=0; i<N; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            inArr[i][j] = Integer.parseInt(stk.nextToken());	
        }
    }
    //run
    for(int i=0;i<N;i++) {
        int[] roadRow = new int[N+1];
        int[] roadCol = new int[N+1];
        for(int j=0;j<N;j++) {
            roadRow[j] = inArr[j][i];
            roadCol[j] = inArr[i][j];
        }
        roadCheck(roadRow); // 행
        roadCheck(roadCol); // 열
    }
    //output
    System.out.println(result);
}

느낀점

생략