[BOJ] 14890.경사로(구현).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

주어진 조건에 맞게 구현을 잘 해주면 되는데,

초반에 어떻게 구현을 할지, 어떤 부분을 함수 처리할지 

먼저 생각해보는게 좋을 것 같다.

너무 복잡하다면 처음에 Naive하게 구현한 후 

함수처리를 하는 것도 좋은 방법이다 !

+

가로 세로를 따로 처리하다보니

디버깅도 어렵고 어느 로직에서 문제가 있는지 찾기가 쉽지 않았다.

그래서 지나갈 수 있는 길을 체크하는 함수를 만들고

각 행, 열을 1차원 배열로 넘겨줬다.

그 다음은 지나갈 수 있는 길인지 체크하는 조건을 잘 확인해주어야 한다.

이전 지형과 높이가 같다면 pass 해주고

이전 지형보다 높이가 1 더 높거나, 1 더 낮을 때 따로 처리를 해주었다.

코드의 주석을 참고하면서 읽어보면 

더 이해가 쉬울 것이다 !

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ14890 {       static int N, X, map[][];       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           st = new StringTokenizer(br.readLine());         N = Integer.parseInt(st.nextToken());         X = 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());             }         }           System.out.println(process());     }       private static int process() {           int res = 0;           for (int i = 0; i < N; i++) {             int[] horizontal = new int[N];             int[] vertical = new int[N];               for (int j = 0; j < N; j++) {                 horizontal[j] = map[i][j];                 vertical[j] = map[j][i];             }               if (check(horizontal)) res++;             if (check(vertical)) res++;         }           return res;     }       private static boolean check(int[] line) {           int cntX = 0;         int now = 0;         int h = line[0];           for (int i = 0; i < N; i++) {             // 이전 지형과 높이가 같다면 pass             if (h == line[i])                 continue;               // 높이의 차가 1보다 크다면 불가능             if (Math.abs(h - line[i]) >= 2) return false;             // 이전 지형보다 1 더 낮다면             else if (h - line[i] == 1) {                 // 경사로를 높을 수 있는지 확인                 now = line[i];                 for (int ck = 0; ck < X; ck++) {                     // 경사로를 놓을 수 없다면                     if (i + ck >= N || now != line[i + ck]) return false;                     // 경사로를 놓았다고 체크                     line[i+ ck] = 10;                 }                 // 경사로 사용                 cntX++;                 // +X+1 부터 다시 확인                 i = i + X - 1;                 if (i >= N) break;             }             // 이전 지형보다 1 더 높다면             else if (h - line[i] == -1) {                 // 경사로를 놓을 수 있는지 확인                 now = line[i];                 for (int ck = 1; ck <= X; ck++) {                     // 경사로를 높을 수 없다면                     if (i - ck < 0 || now - 1 != line[i - ck]) return false;                     // 경사로를 놓았다고 체크                     line[i - ck] = 10;                 }                 // 경사로 사용                 cntX++;             }               h = now;         }           return true;     }   }   Colored by Color Scripter

cs