SEA4014_[모의 SW 역량테스트]활주로 건설

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

문제정리

1. 각 셀의 숫자는 그 지형의 높이를 의미한다.

2. 활주로를 가로 또는 세로 방향으로 건설할 수 있는 가능성을 확인하려고 한다.

3. 활주로는 높이가 동일한 구간에서 건설이 가능하다.

4. 높이가 다른 구간의 경우 활주로가 끊어지기 때문에 경사로를 설치해야만 활주로를 건설 할

수 있다.

5. 경사로는 길이가 X 이고, 높이는 1 이다.

6. 경사로는 높이 차이가 1이고 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에

설치 할 수 있다.

7. 경사로의 길이 X와 절벽지대의 높이 정보가 주어질 때, 활주로를 건설할 수 있는

경우의 수를 계산하는 프로그램을 작성하라.

8. 동일한 셀에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.

9. 경사로는 세워서 사용할 수 없다.

10 입력 T테스트 케이스, N배열 크기, X경사로의 길이

문제issue

1. 경사로를 한번 설치한 곳은 또 설치할 수 없다.

해결흐름

1. 한 행 또는 한 열을 기준으로 살펴본다.

2. 셀에 있는 숫자의 경우는

(1) 계속 똑같은 높이

(2) 높이가 낮아지는 경우

(3) 높이가 높아지는 경우

3. 계속 똑같은 높이라면 활주로 건설이 가능한 곳이다.

4. 높이가 낮아지는 경우와 높아지는 경우라면 경사로를 설치할 수 있는지 살펴본다.

(1) 셀을 이동하다가 숫자가 1 높아지는 경우라면 행을 살펴보고 있었다고 가정했을 때 현재위치를 기준으로(map[i][j]) map[i][j-1]         map[i][j-2]....map[i][j-X]까지 map[i][j]보다 1낮은 숫자였는지 살펴본다.위를 만족한다면 visited을 체크해줘서 한번 경사로를 설치했음을         표시한다.

(2) 셀을 이동하다가 숫자가 1 낮아지는 경우라면 행을 살펴보고 있었다고 가정했을 때 현재위치를 기준으로(map[i][j]) map[i][j+1]         map[i][j+2]...map[i][j+X]까지 map[i][j]보다 1낮은 숫자인지 살펴본다. 위를 만족한다면 visited을 체크해줘서 한번 경사로를 설치했음을         표시한다.

5. 한 번이라도 만족하지 않는다면 그 행 또는 열은 더이상 볼 필요가 없다. 2이상으로 높아지거나 낮아기는 경우에도 더 이상 볼 필요가 없다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int N = Integer.parseInt(st.nextToken());
            int X = Integer.parseInt(st.nextToken());
            int[][] map = new int[N][N];
            boolean[][] visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            // start
            // 행을 살펴본다
            int result = 0;
            for (int i = 0; i < N; i++) {
                here: for (int j = 0; j < N - 1; j++) {
                    // 계속 같은 숫자일 경우
                    if (map[i][j] == map[i][j + 1]) {
                        if (j == N - 2)
                            result++;
                        continue here;
                    }
                    // 높이가 1 낮아지는 경우
                    if (map[i][j] - map[i][j + 1] == 1) {
                        here2: for (int k = 1; k <= X; k++) {
                            if (j + k < N && Math.abs(map[i][j] - map[i][j + k]) == 1 && !visited[i][j + k]) {
                                visited[i][j + k] = true;
                                continue here2;
                            } else {
                                break here;
                            }
                        }
                    }
                    // 높이가 1 높아지는 경우
                    else if (map[i][j + 1] - map[i][j] == 1) {
                        here3: for (int k = 0; k < X; k++) {
                            if (j - k >= 0 && Math.abs(map[i][j - k] - map[i][j + 1]) == 1 && !visited[i][j - k]) {
                                visited[i][j - k] = true;
                                continue here3;
                            } else {
                                break here;
                            }
                        }
                    }
                    // 높이가 2 이상으로 높아지거나 낮아지는 경우
                    else if (Math.abs(map[i][j] - map[i][j + 1]) >= 2) {
                        break here;
                    }
                    // 위를 뚫고 j=N-2까지 와서 살펴봤다면 활주로 건설이 가능한 곳
                    if (j == N - 2)
                        result++;
                }
            }
            // 열을 살펴본다
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                here: for (int j = 0; j < N - 1; j++) {
                    // 계속 같은 숫자일 경우
                    if (map[j][i] == map[j + 1][i]) {
                        if (j == N - 2)
                            result++;
                        continue here;
                    }
                    // 높이가 1 낮아지는 경우
                    if (map[j][i] - map[j + 1][i] == 1) {
                        here2: for (int k = 1; k <= X; k++) {
                            if (j + k < N && Math.abs(map[j][i] - map[j + k][i]) == 1 && !visited[j + k][i]) {
                                visited[j + k][i] = true;
                                continue here2;
                            } else {
                                break here;
                            }
                        }
                    }
                    // 높이가 1 높아지는 경우
                    else if (map[j + 1][i] - map[j][i] == 1) {
                        here3: for (int k = 0; k < X; k++) {
                            if (j - k >= 0 && Math.abs(map[j - k][i] - map[j + 1][i]) == 1 && !visited[j - k][i]) {
                                visited[j - k][i] = true;
                                continue here3;
                            } else {
                                break here;
                            }
                        }
                    }
                    // 높이가 2 이상으로 높아지거나 낮아지는 경우
                    else if (Math.abs(map[j][i] - map[j + 1][i]) >= 2) {
                        break here;
                    }
                    // 위를 뚫고 j=N-2까지 와서 살펴봤다면 활주로 건설이 가능한 곳
                    if (j == N - 2)
                        result++;
                }
            }
            System.out.println("#" + tc + " " + result);
        } // end of tc
    } // end of main
} // end of class