백준 14890 경사로

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

public class Runway {
    static int N;
    static int L;
    static int[][] map;
    static int[][] map2;
    static int[][]visited;
    static int[][]visited2;
    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];
        map2 = new int[N][N];
        visited = new int[N][N];
        visited2 = 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());
                map2[i][j] = map[i][j];
            }
        }
        for(int i = 0; i<N; i++){
            for(int j =0; j<N; j++) {
                xSearch(i,j);
                ySearch(i,j);
            }
        }

        int sum = 0;
        for(int i = 0; i<N; i++){
            int cnt = 1;
            int cnt2 = 1;
            for(int j =0; j<N-1; j++) {
                if (Math.abs(map[i][j] - map[i][j + 1]) > 1 && Math.abs(map2[j][i] - map2[j+1][i]) > 1)
                    break;
                if (map[i][j] == map[i][j + 1]) {
                    cnt++;
                } else if (map[i][j] - map[i][j + 1] == 1 && visited[i][j + 1]==-1) {
                    cnt++;
                } else if (map[i][j + 1] - map[i][j] == 1 && visited[i][j]==1) {
                    cnt++;
                }

                if(map2[j][i]==map2[j+1][i]){
                    cnt2++;
                }
                else if(map2[j][i]-map2[j+1][i]==1 && visited2[j+1][i]==-1){
                    cnt2++;
                }
                else if(map2[j+1][i]-map2[j][i]==1 && visited2[j][i]==1){
                    cnt2++;
                }

            }
            if(cnt==N){
                sum+=1;
            }
            if(cnt2==N) {
                sum += 1;
            }
        }
        System.out.println(sum);

    }
    public static void xSearch(int row,int col){
        if(col==N-1)
            return;
        int downlen = 0;
        int uplen = 0;
        if(map[row][col+1]-map[row][col]==1){
            for(int i = 0; i<L; i++) {
                if(col-i<0||visited[row][col-i] != 0)
                    return;
                if (map[row][col - i] == map[row][col]) {
                    uplen++;
                }
            }
        }
        else if(map[row][col]-map[row][col+1]==1){
            for(int i = 1; i<=L; i++) {
                if(col+i>=N||visited[row][col+i]!=0)
                    return;
                if (map[row][col+i] == map[row][col+1]) {
                    downlen++;
                }
            }
        }
        else{
            return;
        }

        if(uplen>=L){
            for(int i =0; i<L; i++){
                visited[row][col-i] = 1;
            }
        }
        else if(downlen>=L){
            for(int i = 1; i<=L; i++){
                visited[row][col+i] = -1;
            }
        }
    }
    public static void ySearch(int row,int col){
        if(row==N-1)
            return;
        int downlen = 0;
        int uplen = 0;
        if(map2[row+1][col]-map2[row][col]==1){
            for(int i = 0; i<L; i++) {
                if(row-i<0||visited2[row-i][col]!=0)
                    return;
                if (map2[row-i][col] == map2[row][col]) {
                    uplen++;
                }
            }
        }
        else if(map2[row][col]-map2[row+1][col]==1){
            for(int i = 1; i<=L; i++) {
                if(row+i>=N||visited2[row+i][col]!=0)
                    return;
                if (map2[row+i][col] == map2[row+1][col]) {
                    downlen++;
                }
            }
        }
        else{
            return;
        }

        if(uplen>=L){
            for(int i =0; i<L; i++){
                visited2[row-i][col] = 1;
            }
        }
        else if(downlen>=L){
            for(int i = 1; i<=L; i++){
                visited2[row+i][col] = -1;
            }
        }
    }
}

풀이방법

📢이 문제는 가로의 길과 세로의 길을 세는 문제이다. 이문장이 가로의 경사로와 세로의 경사로가 겹쳐도 상관없다는 뜻이라는데.. 좀 모호한거 같지만 이조건을 토대로 문제를 풀었다.
📢 문제를 풀다 보니 map을 변형할 일이 생겨 가로용 map 세로용 map2 2개를 만들었지만, map을 변형하지 않으므로 map은 하나로만 해도 된다.

1. map 탐색시 한방향 탐색만 실시한다.

2. 현재칸에서 오른쪽칸의 높이가 1칸 높고, 왼쪽칸의 높이가 서로 같은 칸이(현재칸 포함) 경사로의 길이보다 같거나 길다면 올라가는 경사로를 만든다. 그리고 경사로의 유무를 체크하는 visited에 1을 대입한다.

3. 현재칸에서 오른쪽칸의 높이가 1칸 낮고, 오른쪽칸의 높이가 서로 같은 칸이(현재칸 제외) 경사로의 길이보다 같거나 길다면,내려가는 경사로를 만든다. 그리고 visited에 -1을 대입한다.
   (이미 경사로가 놓여져 있거나 맵 밖으로 나가지 않도록 주의해서 범위를 설정한다.)

4. 세로 경사로도 같은 방식으로 설계한다. 이때 visited는 이미 변형했으므로, visited2를 생성해서 만든다.

5. 맵을 탑색하며 길이 되는 행, 열을 찾는다. 가로 세로방향의 높이가 2칸이상 차이난다면 그 행, 열은 길이 아니다.

6. 높이가 같거나, 1칸 차이나는 길에 경사로가 있다면 cnt값을 증가시킨다.

7. cnt값과 행,열의 길이가 같다면 길이다.

후기

• 경사로가 있고 없고만 체크했었는데 그러면 3332233 의 경우도 길로 포함시켜 버린다.(내려가는 경사로 이후 다시 올라갈 수 없음) 그래서 내려가는 경사로, 올라가는 경사로로 구분해서 풀었다.
• for문과 if문을 복잡하게 사용하며 풀었고, 범위설정 및 포문의 값 설정이 헷갈려서 실수가 많았다.
• 특별한 알고리즘 없이(완탐인가..?) 복잡한 구현을 성공해서 다행이다.