[JAVA] 백준 (골드3) 14890번 경사로

링크

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

---

입력 예제

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

---

출력 예제

3

---

풀이

지도의 모든 행과 열을 기준으로 탐색을 하며 지나갈 수 있는 길인지의 여부를 확인해야 한다.

for (int i = 0; i < N; i++) {
    //열 기준으로 탐색
    if (isPathValid(map[i])) {
        count++;
    }
    //행 기준으로 탐색
    if (isPathValid(getColumn(i))) {
        count++;
    }
}

지나가는 길이 되려면 다음의 경우를 고려해야 한다.

• 길이 연속으로 높이가 같은지
• 이웃한 길의 높이가 1칸 차이가 날 때
  • 경사로를 놓을 수 있는 경우

//지나갈 수 있는지 여부 반환
private static boolean isPathValid(int[] path) {
    isSlope = new boolean[N];
    
    for (int i = 1; i < N; i++) {
        if (path[i] == path[i - 1]) {  //연속으로 높이가 같을 경우
            continue;
        }
        
        if (path[i] == path[i - 1] + 1) {  //높이가 1칸 높은 경우
            if (canNotPlaceSlope(path, i - L, i - 1, path[i - 1])) {
                return false;
            }
        } else if (path[i] == path[i - 1] - 1) {  //높이가 1칸 낮은 경우
            if (canNotPlaceSlope(path, i, i + L - 1, path[i])) {
                return false;
            }
        } else {  //외의 경우는 모두 불가능
            return false;
        }
    }
    return true;
}

그리고 해당 경사로를 놓을 수 있는 경우는 다음과 같다.

• 지도의 범위를 벗어나지 않은 경우
• 이미 경사로가 놓여있지 않은 경우
• 높이 차이가 1인 경우

//경사로를 놓을 수 있는지 여부 반환
private static boolean canNotPlaceSlope(int[] path, int start, int end, int height) {
    if (start < 0 || end >= N) {  //범위를 벗어난 경우                                       
        return true;                                                                 
    }                                                                                
                                                                                     
    //범위내의 경사로가 있거나 높이가 다른 경우                                                        
    for (int i = start; i <= end; i++) {                                             
        if (isSlope[i] || path[i] != height) {                                       
            return true;                                                             
        }                                                                            
    }                                                                                
                                                                                     
    //범위내에 경사로룰 둔다                                                                   
    for (int i = start; i <= end; i++) {                                            
        isSlope[i] = true;                                                           
    }                                                                                
                                                                                     
    return false;                                                                    

전체 코드

//백준
public class Main {

    private static int[][] map;
    private static boolean[] isSlope;
    private static int N, L;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            //열 기준으로 탐색
            if (isPathValid(map[i])) {
                count++;
            }
            //행 기준으로 탐색
            if (isPathValid(getColumn(i))) {
                count++;
            }
        }

        System.out.println(count);
    }

    //지나갈 수 길인지의 여부 반환
    private static boolean isPathValid(int[] path) {
        isSlope = new boolean[N];

        for (int i = 1; i < N; i++) {
            if (path[i] == path[i - 1]) {  //연속으로 높이가 같을 경우
                continue;
            }

            if (path[i] == path[i - 1] + 1) {  //높이가 1칸 높은 경우
                if (canNotPlaceSlope(path, i - L, i - 1, path[i - 1])) {
                    return false;
                }
            } else if (path[i] == path[i - 1] - 1) {  //높이가 1칸 낮은 경우
                if (canNotPlaceSlope(path, i, i + L - 1, path[i])) {
                    return false;
                }
            } else {  //외의 경우는 모두 불가능
                return false;
            }
        }

        return true;
    }

    //경사로를 놓을 수 있는지 여부 반환
    private static boolean canNotPlaceSlope(int[] path, int start, int end, int height) {
        if (start < 0 || end >= N) {  //범위를 벗어난 경우
            return true;
        }

        //범위내의 경사로가 있거나 높이가 다른 경우
        for (int i = start; i <= end; i++) {
            if (isSlope[i] || path[i] != height) {
                return true;
            }
        }

        //범위내에 경사로룰 둔다
        for (int i = start; i <= end; i++) {
            isSlope[i] = true;
        }

        return false;
    }

    private static int[] getColumn(int colIndex) {
        int[] columns = new int[N];
        for (int i = 0; i < N; i++) {
            columns[i] = map[i][colIndex];
        }
        return columns;
    }
}