[백준] 14890 경사로 - Java

문제

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

 

 

문제 개요

주어진 N×N 크기의 지도에서 행과 열을 기준으로 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 개수를 구하는 문제입니다. 길은 모든 칸의 높이가 같거나, 경사로를 놓아 높이 차이를 극복할 수 있을 때 통과할 수 있습니다. 경사로를 놓을 때는 다음 조건을 만족해야 합니다.

1. 경사로는 낮은 칸에 놓으며, 연속된 L개의 칸에 바닥이 접해야 합니다.
2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 합니다.
3. 낮은 칸은 모두 같은 높이여야 하고, L개 이상 연속되어 있어야 합니다.
4. 경사로가 경사로 위에 중복으로 놓이거나, 범위를 벗어나면 안 됩니다.

 

 

접근 방법

이 문제는 각 행과 열을 각각 확인하면서 조건을 만족하는 길의 개수를 구해야 합니다. 코드는 다음과 같은 순서로 구현되었습니다.

1. 지도 초기화
   입력받은 지도 데이터를 map 배열에 저장하고, N(지도 크기)과 L(경사로 길이)을 초기화합니다.
2. 길 확인 함수
   • 한 행 또는 열을 매개변수로 받아 해당 길이 조건을 만족하는지 확인하는 isPossible 메서드를 구현했습니다.
   • 길이 조건을 만족하는지 확인하기 위해 used 배열을 활용하여 경사로가 이미 놓인 위치를 추적합니다.
3. 조건 검증
   • 인접한 칸의 높이 차이가 1보다 크면 해당 길은 통과 불가능합니다.
   • 경사로를 놓기 위한 낮은 칸 또는 높은 칸이 L개의 연속된 칸을 만족하지 못하면 통과 불가능합니다.
   • 경사로를 놓기 위해 배열 범위를 벗어나는 경우도 제외합니다.
   • 각 칸을 순차적으로 탐색하며 위 조건을 모두 만족하면 해당 길은 통과 가능하다고 판단합니다.
4. 지도 탐색
   • 각 행과 열을 순차적으로 탐색하며 isPossible 메서드를 호출하여 통과 가능한 길의 개수를 확인합니다.
   • 각 행은 그대로 탐색하며, 각 열은 새로운 배열에 저장하여 탐색합니다.

 

 

코드

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

public class Main {
    static int N, L;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(checkMap());
    }

    public static int checkMap() {
        int cnt = 0;

        for(int[] row : map) {
            if(isPossible(row)) cnt++;
        }

        for(int i=0; i<N; i++) {
            int[] col = new int[N];
            for(int j=0; j<N; j++) {
                col[j] = map[j][i];
            }
            if(isPossible(col)) cnt++;
        }

        return cnt;
    }

    public static boolean isPossible(int[] arr) {
        boolean[] used = new boolean[N];

        for(int i=0; i<N - 1; i++) {
            if(arr[i] == arr[i+1]) continue;
            if(Math.abs(arr[i] - arr[i+1]) > 1) return false;

            if(arr[i] < arr[i+1]) {
                if(i - L  + 1 < 0) return false;
                for(int j=i-L+1; j<=i; j++) if(arr[j] != arr[i] || used[j]) return false;
                for(int j=i-L+1; j<=i; j++) used[j] = true;
            } else {
                if(i+L >= N) return false;
                for(int j=i+1; j<=i+L; j++) if(arr[j] != arr[i+1] || used[j]) return false;
                for (int j=i+1; j<=i+L; j++) used[j] = true;
            }
        }

        return true;
    }

    public static void init() throws IOException {
        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++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}