BOJ 14890 경사로(Java)

문제 탐색하기

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

• 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.
  • 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

길을 지나갈 수 있으려면

1. 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는,
2. 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.

경사로는

• 높이가 항상 1이며, 길이는 L이다.
• 개수는 매우 많아 부족할 일이 없다.

• 경사로는 낮은 칸과 높은 칸을 연결한다

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

코드 설계하기

구현 방법

1. 지도 처리
   • N×N 크기의 2차원 배열로 지도를 입력받음
   • 가로(행) 방향과 세로(열) 방향을 각각 검사해야 함
   • 세로 방향 검사를 위해 지도를 전치(transpose)하여 처리
2. 경로 검사 로직 (checkPath 메서드)
   • 한 줄(행 또는 열)을 입력받아 지나갈 수 있는지 검사
   • used 배열로 경사로가 설치된 위치를 체크
   • 인접한 칸들의 높이 차이를 검사:
     1. 높이가 같으면 (diff = 0) 계속 진행
     2. 높이 차가 1이면 (diff = 1 또는 -1) 경사로 설치 가능 여부 확인
     3. 높이 차가 2 이상이면 불가능
3. 경사로 설치 검사
   • 뒤가 1 더 높은 경우 (diff = 1):
     • 현재 위치에서 왼쪽으로 L칸이 같은 높이인지 확인
     • 범위를 벗어나거나, 높이가 다르거나, 이미 경사로가 있으면 실패
   • 앞이 1 더 높은 경우 (diff = -1):
     • 다음 위치에서 오른쪽으로 L칸이 같은 높이인지 확인
     • 동일한 조건 검사

시간 복잡도

• 입력: O(N²) - N×N 크기의 지도 입력
• 지도 전치: O(N²) - N×N 배열의 전치 연산
• 경로 검사:
  • 각 줄마다 O(N) 시간 소요
  • 가로 N줄, 세로 N줄 검사: O(N) × 2N = O(N²)
• 전체 시간 복잡도: O(N²)
  • N ≤ 100이므로 충분히 시간 내에 해결이 가능하다.

정답 코드 (Java)

package gold;

import java.io.*;
import java.util.*;

public class b14890 {
    private static int[][] map;
    private static int N, L;
    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());
            }
        }
        int res = 0;
        // 가로 방향
        for (int[] arr : map) {
            if (checkPath(arr)) res++;
        }

        int[][] transposed = transpose(map);

        // 세로 방향
        for (int[] arr : transposed) {
            if (checkPath(arr)) res++;
        }

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

    private static int[][] transpose(int[][] arr) {
        int[][] res = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[j][i] = arr[i][j];
            }
        }
        return res;
    }

    private static boolean checkPath(int[] line) {
        boolean[] used = new boolean[N];
        for (int i = 0; i < N - 1; i++) {
            int diff = line[i + 1] - line[i];

            if (diff == 0) continue;
            else if (diff == 1) {
                // 뒤가 1 더 높으면 i에서부터  왼쪽으로 L칸 확인
                for (int j = i; j > i - L; j--) {
                    if (j < 0 || line[j] != line[i] || used[j]) return false;
                    used[j] = true;
                }
            } else if (diff == -1) {
                // 앞이 1 더 높으면 i+1부터 오른쪽으로 L칸 확인
                for (int j = i + 1; j <= i + L; j++) {
                    if (j >= N || line[j] != line[i + 1] || used[j]) return false;
                    used[j] = true;
                }
            } else // 단차가 2 이상이면 경사로 배치 불가능
                return false;
        }
        return true;
    }
    
}