[백준] 경사로 14890 java - 구현

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

 

문제를 이해하는 데에 시간을 꽤나 썼다..

하지만 문제를 이해하면 조건만 잘 체크해주면 풀이가 수월하다 !

<열을 이동하면서 체크/행을 이동하면서 체크>

2개의 경우로 나누어서 알고리즘을 짰다

이 두 경우 인덱스 순서만 바꿔주면 되고 알고리즘은 동일하기 때문에 열을 이동하는 경우를 생각하면

1열의 경우 1~N행 반복문을 돌면서 값이 달라지는 경우에 경사로를 만들 수 있는지 확인하면 된다

값이 같은 경우는 생각할 필요 없으므로 continue

예를 들어, 1행과 2행의 값이 2로 같다면 경사로를 만들 필요가 없으므로 건너 뜀!

 

따라서 값이 달라지는 경우 경사로를 만들 수 있는지를 체크해주는게 키포인트다!

경사로 조건은 다음과 같다

1) 경사로를 만드는 곳은 두 값의 차이 중 값이 작은 부분!

2) 값의 차이가 1

3) 이전에 경사로를 만든적이 있으면 x (visited 체크)

 

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[][] graph = new int[N][N];
        boolean[][] visited = new boolean[N][N];

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int cnt = 0;
        for(int i=0;i<N;i++){
            boolean flag = false;

            for(int j=1;j<N;j++){
                if(graph[i][j-1]==graph[i][j]){
                    continue;
                }

                if(graph[i][j-1]>graph[i][j] && j+L-1<N && graph[i][j-1]-graph[i][j+L-1]==1 && !visited[i][j+L-1]){
                    for(int k=j;k<=j+L-1;k++){
                        visited[i][k] = true;
                    }
                } else if(graph[i][j-1]<graph[i][j] && j-L>=0 && graph[i][j]-graph[i][j-L]==1 && !visited[i][j-L]){
                    for(int k=j-1;k>j-L-1;k--){
                        visited[i][k] = true;
                    }
                } else {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                cnt++;
            }
        }

        visited = new boolean[N][N];

        for(int i=0;i<N;i++){
            boolean flag = false;

            for(int j=1;j<N;j++){
                if(graph[j-1][i]==graph[j][i]){
                    continue;
                }

                if(graph[j-1][i]>graph[j][i] && j+L-1<N && graph[j-1][i]-graph[j+L-1][i]==1 && !visited[j+L-1][i]){
                    for(int k=j;k<=j+L-1;k++){
                        visited[k][i] = true;
                    }
                } else if(graph[j-1][i]<graph[j][i] && j-L>=0 && graph[j][i]-graph[j-L][i]==1 && !visited[j-L][i]){
                    for(int k=j-1;k>j-L-1;k--){
                        visited[k][i] = true;
                    }
                } else {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}