BOJ_14890 : 경사로

👉 문제링크

14890번: 경사로

---

---

🔸 문제 분석 🔸

•  N x N 지도에서 지나갈 수 있는 길이 몇 개인지 출력한다.
  • 길을 지나가려면 높이가 모두 같거나, 경사로를 설치해야 한다.
  • 경사로는 높이 차이가 1이고, L 만큼의 공간이 확보되어야 한다.
  • 또, 경사로는 반대 방향으로 겹칠 수 없고, 맵을 벗어나서는 안된다. (가로,세로는 겹쳐도 된다)
• 행과 열 한 줄씩 복사해서 확인하는 방식으로 지나갈 수 있는 길을 카운트한다.
  • 경사로를 놓은 곳을 체크하면서 지나갈 수 있는지 확인한다.

🔸 코드 🔸

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

public class Main {
    private static int N, L;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        int[][] 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());
            }
        }

        // 한 줄씩 복사 후 확인
        int[] line = new int[N];
        int ans = 0;

        for (int i = 0; i < N; i++) {
            // 행 복사
            for (int j = 0; j < N; j++)
                line[j] = map[i][j];

            if (lineCheck(line))
                ans++;

            // 열 복사
            for (int j = 0; j < N; j++)
                line[j] = map[j][i];

            if (lineCheck(line))
                ans++;
        }

        // Output
        System.out.print(ans);
    }

    private static boolean lineCheck(int[] line) {
        boolean[] check = new boolean[N];
        for (int i = 1; i < N; i++) {
            int gab = Math.abs(line[i] - line[i-1]);
            if (gab > 1) return false;
            else if(gab == 1) { // 경사로 놓아야 함
                if (line[i-1] > line[i]) {  // 앞쪽이 더 큰 경우 -> 뒤에 L크기 공간 필요
                    for (int j = i; j < i+L; j++) {
                        if (j >= N || check[j] || line[j] != line[i]) return false; // 맵을 벗어남, 겹침, 공간 없으면 경사로 못놓음
                        check[j] = true;
                    }
                } else {                    // 뒤쪽이 더 큰 경우 -> 앞에 L크기 공간 필요
                    for (int j = i-1; j > i-1-L; j--) {
                        if (j < 0 || check[j] || line[j] != line[i-1]) return false; // 맵을 벗어남, 겹침, 공간 없으면 경사로 못놓음
                        check[j] = true;
                    }
                }
            }
        }
        return true;
    }
}

🔸 코드 해석 🔸

• 지도의 행 또는 열을 line 배열에 복사해서 lineCheck 메서드로 지나갈 수 있는 길인지 확인한다.
  • 경사로를 놓은 곳은 check 배열을 true로 변경한다.
  • 인덱스를 하나씩 증가해 가며 인접 인덱스를 비교한다.
    • 높이 차이가 1을 넘으면 지나갈 수 없으므로 false를 반환한다.
    • 높이차이가 1이면 경사로를 놓을 수 있는지 확인한다.
      • 앞쪽, 뒤쪽을 구분해 L만큼 공간이 있는지 확인한다.
      • 놓을 수 없으면 false를 반환한다.
  • 높이가 모두 같거나, 경사로를 설치해 해결했으면 true를 반환한다.

---

🔸 end 🔸

• 행이든 열이든 1차원 배열 line에 복사해서 검사하므로써 중복 코드를 줄일 수 있는게 핵심 아이디어였던 것 같다.