[BOJ 14890] 경사로 - JAVA, Gold3

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

14890번: 경사로

 

[문제 유형 : 구현]

📌구현할 기능 목록📌

1. 지도의 크기(N)와 경사로의 길이(L)를 입력받는다.

 

2. 지도의 각 위치별 높낮이를 입력받고 2차원 배열에 저장한다.

 

3. 지도에서의 한 열을 1차원 배열로 변환시켜줄 수 있는 메서드를 작성한다.

 

4. 매개변수로 전해받은 1차원 배열에 대해서 경사로를 사용해 지나갈 수 있는지 검사하는 메서드를 작성한다.

 - 아래의 3가지 경우를 생각하여 구현 로직을 달리한다.

  1) 이전 블록이 다음 블록보다 1 더 작은 경우

  2) 이전 블록이 다음 블록보다 1 더 큰 경우

  3) 이전 블록과 다음 블록의 오차가 2 이상인 경우

 

5. 각 행과 열을 지나갈 수 있는지 각각 검사하고, 결과인 지나갈 수 있는 길의 개수를 출력한다.

 

💻코드 적용💻

1. 지도의 크기(N)와 경사로의 길이(L)를 입력받는다.

N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());

 

2. 지도의 각 위치별 높낮이를 입력받고 2차원 배열에 저장한다.

map = new int[N][N];

for(int i=0;i<N;++i){
    st = new StringTokenizer(br.readLine());
    for(int j=0;j<N;++j){
        map[i][j]=Integer.parseInt(st.nextToken());
    }
}

 

3. 지도에서의 한 열(세로줄)을 하나의 1차원 배열로 변환시켜줄 수 있는 메서드를 작성한다.

static int[] transferColumnArray(int columnIndex){
    int resultArray[] = new int[N];
    for(int i=0;i<N;++i){
        resultArray[i]=map[i][columnIndex];
    }
    return resultArray;
}

 

4. 매개변수로 전해받은 1차원 배열에 대해서 경사로를 사용해 지나갈 수 있는지 검사하는 메서드를 작성한다.

 - 아래의 3가지 경우를 생각하여 구현 로직을 달리한다.

  1) 이전 블록이 다음 블록보다 1 더 작은 경우

  2) 이전 블록이 다음 블록보다 1 더 큰 경우

  3) 이전 블록과 다음 블록의 오차가 2 이상인 경우

static int result=0; // 

static void checkCanPass(int arr[]){
    boolean isUsed[] = new boolean[N]; // 해당 좌표에 경사로가 놓여있는지 확인하는 변수

    for(int i=0;i<N-1;++i){
        // 이전 블록이 다음 블록보다 1 작은 경우
        if(arr[i]==arr[i+1]-1){
            if(i-L+1>=0){ // i-L+1은 이전 블록 포함 앞으로 L번 갔을 때의 인덱스
                for(int j=i-L+1;j<i+1;++j){
                    if(isUsed[j] || arr[j]!=arr[i]) return; // 이미 경사로가 놓여있거나 높이가 다른경우
                    isUsed[j]=true;
                }
            }
            else return; // 인덱스가 0이하로 간 경우 함수 종료
        }
        // 이전 블록이 다음 블록보다 1 큰 경우
        else if(arr[i]==arr[i+1]+1){
            if(i+L<N){ // i+L은 다음 블록 포함 뒤로 L번 갔을 때의 인덱스
                for(int j=i+1;j<=i+L;++j){
                    if(isUsed[j] || arr[j]!=arr[i+1]) return; // 이미 경사로가 놓여있거나 높이가 다른경우
                    isUsed[j]=true;
                }
            }
            else return; // 인덱스가 N이상으로 간 경우 함수 종료
        }
        // 이전 블록과 다음 블록의 오차가 2 이상인 경우
        else if(arr[i]!=arr[i+1]) return;
    }
    ++result; // 함수가 문제없이 종료되었을 경우로, 해당 경로가 이동 가능한 것이기 때문에 result+1
}

여기서 주의할 점이 하나있다.

 

각 좌표에는 경사로가 하나만 놓일 수 있느나,

이것은 하나의 열과 행을 검사할 때를 별개의 경우로 생각을 해야한다는 점이다.

 

예로 N=6, L=2 (N: 지도의 크기, L: 경사로의 길이)일 때, 아래와 같은 지도가 있다면

3행의 0,1번 인덱스에 경사로를 두어 지나갈 수 있게 한다면,

2의 2,3번 인덱스에 경사로를 두면 먼저 설치해둔 경사로 때문에 해당 좌표에 경사로를 둘 수 없다고 생각할 수 있다.

 

하지만 이는 별개다.

3행 통과하기 위한 경사로를 둘 수 있고, 2열을 통과하기 위한 경사로 또한 둘 수 있다.

 

따라서 각 행과 열에 별개의 검사를 시행하여 경사로를 둠으로서 지나갈 수 있는지 확인해야한다.

 

5. 각 행과 열을 지나갈 수 있는지 각각 검사하고, 결과인 지나갈 수 있는 길의 개수를 출력한다.

// 행 검사
for(int i=0;i<N;++i){
    checkCanPass(map[i]);
}

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

bw.write(result+"\n");
bw.flush();
bw.close();

 

⌨제출한 코드⌨

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static int N,L;
    static int map[][];

    static int result=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        // 행 검사
        for(int i=0;i<N;++i){
            checkCanPass(map[i]);
        }

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

        bw.write(result+"\n");
        bw.flush();
        bw.close();
    }

    static int[] transferColumnArray(int columnIndex){
        int resultArray[] = new int[N];
        for(int i=0;i<N;++i){
            resultArray[i]=map[i][columnIndex];
        }
        return resultArray;
    }

    static void checkCanPass(int arr[]){
        boolean isUsed[] = new boolean[N];

        for(int i=0;i<N-1;++i){
            if(arr[i]==arr[i+1]-1){ // 이전 블록이 다음 블록보다 1 작은 경우
                if(i-L+1>=0){
                    for(int j=i-L+1;j<i+1;++j){
                        if(isUsed[j] || arr[j]!=arr[i]) return;
                        isUsed[j]=true;
                    }
                }
                else return;
            }
            else if(arr[i]==arr[i+1]+1){ // 이전 블록이 다음 블록보다 1 큰 경우
                if(i+L<N){
                    for(int j=i+1;j<=i+L;++j){
                        if(isUsed[j] || arr[j]!=arr[i+1]) return;
                        isUsed[j]=true;
                    }
                }
                else return;
            }
            else if(arr[i]!=arr[i+1]) return;
        }
        ++result;
    }
}