백준 14890. 경사로 :: 돼지개발자

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

"시뮬레이션"

해당 문제는 다리를 놓을 수 있느냐 없느냐 를 판별하는 것이 핵심인 문제로 아래와 같이 경사로는 두 가지로 분류할수 있다.

내려가는 경사로와 올라가는 경사로가 둘다 비슷하지만 조금 다른 부분이 있다. 내려가는 경사로의 경우 경사로가 이전에 방문하지 않았던 칸으로 놓이기 때문에, 경사로 설치 여부 체크를 하지 않아도 된다.

하지만 올라가는 경사로의 경우 이전에 방문했던 칸에 경사로를 놓아야 하기 때문에 이전에 경사로를 놓아 지금 칸에 도착한 것인지 판별해야한다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int n,l, cnt;
    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());
            }
        }
        
        for (int i = 0; i < n; i++) {
            if(solve(map[i])) cnt++;
            
            int[] temp = new int[n];
            
            for (int j = 0; j < n; j++) {
                temp[j] = map[j][i];
            }
            if(solve(temp)) cnt++;
        }
        
        System.out.println(cnt);
    }
    
    static boolean solve(int[] arr) {
        int idx = 0;
        boolean[] visited = new boolean[n];
        
        while(true) {
            // 끝까지 도달.
            if(idx == n-1) break;
            
            // 내려가는 경사로인 경우
            if(arr[idx+1] == arr[idx] - 1) {
                if(idx + l >= n ) return false;
                
                for (int i = idx+1; i <= idx+l; i++) {
                    visited[i] = true;
                    if(arr[i] != arr[idx] -1)
                        return false;
                }
                idx += l;
            }
            // 올라가는 경사로인 경우
            else if(arr[idx+1] == arr[idx] + 1) {
                if( idx - (l-1) < 0 ) return false;
                
                for (int i = idx-(l-1); i <= idx; i++) {
                    if(visited[i] || arr[i] != arr[idx])
                        return false;
                }
                idx++;
            }
            // 평지인 경우
            else if(arr[idx] == arr[idx+1]) {
                idx++;
            }
            // 높이 차이가 2 이상인 경우, 못지나감.
            else {
                return false;
            }
        }
        return true;
    }
 
}