[백준]JAVA - 14890번: 경사로

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

14890번: 경사로

풀이

처음에 문제를 잘 못 이해해서 꽤 오랫동안 고민했다.

 

우선 모든 행과 열을 한 줄로 나열해서 체크해야 한다. 

예를 들어, 위 그림처럼 6x6 행렬이 있다면 행 6번, 열 6번 총 12번의 체크를 해야 한다.

for (int i=0; i<N; i++) {
    if (Check(i, 0, 0)) ans++;
    if (Check(0, i, 1)) ans++;
}

검사를 시작할 때 행과 열을 구분하기 위해서 세 번째 인자를 넣어줬다. 이후에 쉽게 검사를 진행하기 위해서 1차원 배열에 옮겼다.

 

길을 통과하기 위해선 해당 경로의 모든 높이가 같아야 하며, 인접한 경로의 높이가 1 차이가 있다면 L 길이의 경사로를 놓을 수 있다. 

 

1차원 배열로 옮겨 담은 값을 하나씩 비교해본다. 모든 높이가 같을 경우엔 true를 넘겨주면 된다. 

L 길이의 경사로를 놓으려면 높이 차이가 2 이상이면 안되기 때문에 예외처리도 해준다.

if (SlopeWay[i] == SlopeWay[i+1]) {
    continue;
}
                
if (Math.abs(SlopeWay[i] - SlopeWay[i+1]) > 1) {
    return false;
}

이젠 경사로를 놓았을 때의 경우만 생각하면 된다. 경사로를 놓았을 때 생기는 경우의 수는 2가지이다.

1. 오르막 길
2. 내리막 길

오르막 길, 내리막 길까지 생각했다면 다음은 경사로를 놓을 수 있는 조건도 생각해야 한다.

1. L 길이의 경사로가 배열의 크기를 벗어나지 않아야함 
2. 경사로를 놓는 경로의 높이는 같아야함
3. 경사로를 여러 개 겹쳐서 놓을 수 없음 (visited 처리)

<최종코드>

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

public class Main {
    static int N, L;
    static int[][] map;
    
    public static void main(String[] args) 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());
            }
        }
	    
        int ans = 0;
        for (int i=0; i<N; i++) {
            if (Check(i, 0, 0)) ans++;
            if (Check(0, i, 1)) ans++;
        }
	    
        System.out.println(ans);
    }
    
    public static boolean Check(int x, int y, int d) {
        int[] SlopeWay = new int[N];
        boolean[] visited = new boolean[N];
        
        for (int i=0; i<N; i++) {
            SlopeWay[i] = (d == 0) ? map[x][y+i] : map[x+i][y];
        }
        
        for (int i=0; i<N-1; i++) {
            if (SlopeWay[i] == SlopeWay[i+1]) {
                continue;
            }
                
            if (Math.abs(SlopeWay[i] - SlopeWay[i+1]) > 1) {
                return false;
            }
            
            // 내리막길
            if (SlopeWay[i] -1 == SlopeWay[i+1]) {
                for (int j=i+1; j<i+1+L; j++) {
                    if (j > N-1 || SlopeWay[i+1] != SlopeWay[j] || visited[j]) {
                        return false;
                    }
                    visited[j] = true;
                }
            }
            
            // 오르막길
            if (SlopeWay[i] + 1 == SlopeWay[i+1]) {
                for (int j=i; j>i-L; j--) {
                    if (j < 0 || SlopeWay[i] != SlopeWay[j] || visited[j]) {
                        return false;
                    }
                    visited[j] = true;
                }
            }
        }
        
        return true;
    }
}

내가 생각한 시간 복잡도: O($n^{2}$)