경사로 ( java )

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

 

위의 문제를 이해하는데에 시간이 조금 걸렸습니다.

 

[ 문제 해석 ]

 

1. 문제의 목표

한 행 또는 한 열 전부에서 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 갯수를 구해라

 

N*N 배열에 각 숫자들이 들어가 있습니다.

그 숫자들은 각각의 높이를 가리킵니다.

아래 배열 표에서 1행은 각각 3 3 3 3 3 3 의 높이를 가집니다.

 

2. 지나갈 수 있는 조건

 1) 길에 속한 모든 칸의 높이가 같은 경우

 2) 또는 지나갈 수 있는 경사로를 만들어서 지나가는 방법

 

 

3. 경사로의 특징

 1) 높이 차이가 항상 1이다.

 2) 경사로는 낮은 칸에 놓는다.

 3) L개의 연속된 칸에 경사로 바닥이 모두 접해야 한다.

 4) 경사로를 놓을 낮은 칸의 높이는 모두 같아야 한다.

 

 

4. 경사로를 놓지 못하는 경우

 1) 경사로를 놓은 곳에 또 경사로를 놓는 경우

 2) 낮은 칸과 높은 칸의 차이가 1이 아닌 경우

 3) 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않는 경우

 4) 경사로 때문에 배열의 범위를 벗어난 경우

 

 

[ 경사로 놓을 수 있는 예시 ]

 

 

[ 경사로를 놓지 못하는 경우 ]

왼쪽부터 1,2,3,4 번으로 부르겠습니다.

- 1번 : 높이 1을 높여도 3까지 닿지 못함

- 2번 : 경사로 바닥이 닿지 않음

- 3번 : 경사로가 겹침

- 4번 : 경사로 바닥이 닿지 않음

 

 

[ 문제 풀이 과정 ]

1. 행과 열에서 지나갈 수 있는 길을 구하는 함수를 각각 만들어 준다.

2. 만약 있는 경우 1을 return 하고, 없는 경우 0을 return 하여 각 행렬을 모두 순회한다.

3. 함수 내부에서 N만큼의 크기를 갖는 Buffer 라는 임시 배열을 만든다.

4. 만약 road 배열에서 해당 인덱스 다음 인덱스가 숫자가 더 크면 오르막길이고, 낮으면 내리막길이다.

5. 내리막길인 경우, i인덱스에 올라올 수 있는 길을 만들어야 하므로 i의 다음 인덱스부터 L까지에 해당하는 경사로를 놓아준다.

6. 만약 위의 경사로를 놓을 수 없는 경우가 없다면 Buffer에 해당 자리의 카운트를 증가시킨다.

7. 행을 탐색한 경우 모든 행을 탐색하고 마지막으로 Buffer 내부 원소 값을 비교해 1보다 큰 경우 중첩되는 경우 이므로,

   갈 수 없는 길로 0을 리턴해준다.

8. 모든 조건이 맞는다면 1을 리턴해준다.

 

이와 같은 방식을 행열에 모두 적용해주면 됩니다.

 

[ 소스코드 ]

import java.util.Scanner;

public class 경사로 {

    // 백준 코드로 제출시 Main 으로 제출

    // 입력
    static int N, L;
    static int answer = 0;
    static int[][] road;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();

        road = new int[N][N];

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

        for (int i = 0; i < N; i++) {
            answer += roadCol(i) + roadRow(i);
        }

        System.out.println(answer);
    }

    public static int roadCol(int idx) {

        int[] Buffer = new int[N]; // 초기값 : 0

        // 만약 배열이 차이가 없는 경우에는 초기 값이 그대로 유지됨

        for (int i = 0; i < N; i++) {

            //높이 차이가 2이상 나는 경우
            try {
                if (road[idx][i] >= road[idx][i + 1] + 2) {
                    return 0;
                }
                if (road[idx][i] <= road[idx][i + 1] - 2) {
                    return 0;
                }

                if (road[idx][i] > road[idx][i + 1]) { // 내리막
                    int start = i + 1;
                    int j;
                    for (j = start; j < start + L; j++) {
                        if (j >= N) return 0; // 범위를 벗어난 경우
                        if (road[idx][i + 1] == road[idx][j]) { // 다음 블럭의 높이가 같은 경우 버퍼에 넣어줌
                            Buffer[j]++;
                        } else return 0;
                    }
                }
                else if (road[idx][i] < road[idx][i + 1]) { // 오르막
                    int start = i;
                    int j;
                    for (j = start; j > start - L; j--) {
                        if (j < 0) return 0; // 범위가 넘으면 종료
                        if (road[idx][i] == road[idx][j]) {
                            Buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(Buffer[i] > 1) return 0;
        }

        return 1;
    }

    public static int roadRow(int idx) {
        int[] buffer = new int[N];

        for (int i = 0; i < N; i++) {
            try {
                if (road[i][idx] >= road[i + 1][idx] + 2) {
                    return 0;
                }
                if (road[i][idx] <= road[i + 1][idx] - 2) {
                    return 0;
                }

                if (road[i][idx] > road[i + 1][idx]) { // 오르막
                    int start = i + 1;
                    for (int j = start; j < start + L; j++) {
                        if (j >= N) return 0;
                        if (road[i + 1][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }

                if (road[i][idx] < road[i + 1][idx]) { // 내리막
                    int start = i;
                    for (int j = start; j > start - L; j--) {
                        if (j < 0) return 0;
                        if (road[i][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(buffer[i] > 1) return 0;
        }

        return 1;
    }
}

 

 

 

[ 참고 ]

백준에서 코드 제출할 때는 클래스 명을 Main 으로 작성해서 제출해야 합니다.

위의 코드를 그대로 제출할 시 컴파일 에러가 발생합니다.

 

 

* 참조 : https://www.youtube.com/watch?v=PCURy3Wv8uU