경사로

📍 문제 설명

 

💡 접근

모든 행에 대해서 모든 열까지 갈 수 있는지, 모든 열에서 모든 행까지 갈 수 있는지 판단해주면 되는 문제였다.

1.bfs 풀이와 비슷하게 큐를 이용하였고 바로 이동하든 경사로를 설치해서 이동하든 이동된 좌표를 큐에 넣어주었다.

2.(0, 0) 좌표는 행의 끝, 열의 끝 모두 판단해줘야하기 때문에 kind로 판단해주었다.

3.경사로가 겹치는 경우엔 설치를 하지 못하므로 설치할 때 설치가 된 모든 좌표에 대해서 설치 되었다고 체크해주었다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k, answer, cnt, max, min, sum, count, l;
    static int[][] board, clone, dis;
    static boolean[][] visited;
    static int[] ch, pm, combi, graph, temp;
    static boolean flag = false;
    static int[] dx = {-1,0,1,0,}; //북동남서
    static int[] dy = {0,1,0,-1};
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        l = kb.nextInt();
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //0,0 -> 0,7로 갈 수 있냐
        //1,0 -> 1,7로 갈 수 있냐
        //0,0 -> 7,0로 갈 수 있냐
        //0,1 -> 7,1로 갈 수 있냐 ....

        //0,0 1,0 2,0 3,0 4,0 5,0 - 끝 열(6)까지 갈 수 있나 확인
        //0,0 0,1 0,2 0,3 0,4 0,5 - 끝 행(6)까지 갈 수 있나 확인

        //겹치게 못까는거, 그리고 경사로 범위?
        for(int i = 0; i < n; i++) {
            T.solution(i, 0, 0);
            T.solution(0, i, 1);
        }
        System.out.println(answer);
    }

    private void solution(int x, int y, int kind) {
        //경사로 사용여부
        visited = new boolean[n][n];
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y));
        //경사로를 놓을 수 있는 경우
        //현재 좌표의 값이 L까지의 좌표의 값이 -1 이어야 한다.
        //현재 좌표의 값이 L이전까지는 동일하고 L일 때 +1 이어야 한다.

        //경사로 설치 가능여부
        flag = true;

        while(!q.isEmpty()) {
            Point cp = q.poll();
            //현재 좌표에서 끝 열까지 갈 수 있는지 확인
            if (y == 0 && kind == 0) {
                int ny = cp.y + 1;
                //도착지점에 도착했다!
                if(ny == n) {
                    answer++;
                    break;
                }

                //경사로 없이 그냥 갈 수 있으면 바로 이동
                if(board[cp.x][cp.y] == board[cp.x][ny]) {
                    q.offer(new Point(cp.x, ny));
                }
                //현재 지점이 다음 지점보다 1 더 크면 다음 지점에서 경사로의 길이만큼 값이 같아야 놓을 수 있음 + 다음 지점 경사로 설치 X
                else if (board[cp.x][cp.y] > board[cp.x][ny] && board[cp.x][cp.y] - board[cp.x][ny] == 1 && !visited[cp.x][ny]) {
                    //다음 지점에서 경사로의 길이만큼 값들이 서로 같아야함
                    for(int i = 1; i < l; i++) {
                        int nny = ny + i;
                        //범위를 벗어나면 경사로를 놓을 수 없음 / 값이 같지 않아도 놓을 수 없음 / 설치된 곳도 설치할 수 없음
                        if(nny >= n || board[cp.x][ny] != board[cp.x][nny] || visited[cp.x][nny]) {
                            flag = false;
                            break;
                        }
                    }
                    //경사로 설치 가능하면 바로 경사로 다음 지점으로 이동 + 경사로 설치한 좌표들 모두 설치
                    if(flag) {
                        q.offer(new Point(cp.x, cp.y + l));
                        //다음 지점 경사로 설치
                        visited[cp.x][ny] = true;
                        //경사로의 길이만큼 경사로 설치
                        for(int i = 1; i < l; i++) {
                            int nny = ny + i;
                            visited[cp.x][nny] = true;
                        }
                    }
                }
                //현재 지점이 다음 지점 보다 1 더 작으면 현재 지점을 포함하여 경사로의 길이만큼 값이 같아야 놓을수 있음 + 현재 지점 설치된 곳도 설치 못함
                else if (board[cp.x][cp.y] < board[cp.x][ny] && board[cp.x][cp.y] - board[cp.x][ny] == -1 && !visited[cp.x][cp.y]) {
                    //현재 지점포함 경사로의 길이만큼 이전 값들의 값이 서로 같아야함
                    for(int i = 1; i < l; i++) {
                        int nny = cp.y - i;
                        //범위를 벗어나면 경사로를 놓을 수 없음 / 값이 같지 않아도 놓을 수 없음 + 설치된 곳도 설치할 수 없음
                        if(nny >= n || nny < 0 || board[cp.x][cp.y] != board[cp.x][nny] || visited[cp.x][nny]) {
                            flag = false;
                            break;
                        }
                    }
                    //경사로 설치 가능하면 바로 다음 지점으로 이동 + 경사로 설치한 좌표들 모두 방문처리
                    if(flag) {
                        q.offer(new Point(cp.x, ny));
                        //현재 지점 경사로 설치
                        visited[cp.x][cp.y] = true;
                        //경사로의 길이 만큼 경사로 설치
                        for(int i = 1; i < l; i++) {
                            int nny = cp.y - i;
                            visited[cp.x][nny] = true;
                        }
                    }
                }
            }

            //현재 좌표에서 끝 행까지 갈 수 있는지 확인
            else if (x == 0 && kind == 1) {
                int nx = cp.x + 1;
                //도착지점에 도착했다!
                if(nx == n) {
                    answer++;
                    break;
                }

                //경사로 없이 그냥 갈 수 있으면 바로 이동
                if(board[cp.x][cp.y] == board[nx][cp.y]) {
                    q.offer(new Point(nx, cp.y));
                }
                //현재 지점이 다음 지점보다 1 더 크면 다음 지점에서 경사로의 길이만큼 값이 같아야 놓을 수 있음 + 설치된 곳 설치할 수 없음
                else if (board[cp.x][cp.y] > board[nx][cp.y] && board[cp.x][cp.y] - board[nx][cp.y] == 1 && !visited[nx][cp.y]) {
                    //다음 지점에서 경사로의 길이만큼 값들이 서로 같아야함
                    for(int i = 1; i < l; i++) {
                        int nnx = nx + i;
                        //범위를 벗어나면 경사로를 놓을 수 없음 / 값이 같지 않아도 놓을 수 없음 + 설치된 곳 설치할 수 없음
                        if(nnx >= n || board[nx][cp.y] != board[nnx][cp.y] || visited[nnx][cp.y]) {
                            flag = false;
                            break;
                        }
                    }
                    //경사로 설치 가능하면 바로 경사로 지점으로 이동 + 경사로 설치한 좌표들 모두 방문처리
                    if(flag) {
                        q.offer(new Point(cp.x + l, cp.y));
                        //다음
                        visited[nx][cp.y] = true;
                        //경사로의 길이만큼 경사로 설치
                        for(int i = 1; i < l; i++) {
                            int nnx = nx + i;
                            visited[nnx][cp.y] = true;
                        }
                    }
                }
                //현재 지점이 다음 지점 보다 1 더 작으면 현재 지점을 포함하여 경사로의 길이만큼 값이 같아야 놓을수 있음 + 설치된 곳 설치할 수 없음
                else if (board[cp.x][cp.y] < board[nx][cp.y] && board[cp.x][cp.y] - board[nx][cp.y] == -1 && !visited[cp.x][cp.y]) {
                    //현재 지점포함 경사로의 길이만큼 이전 값들의 값이 서로 같아야함
                    for(int i = 1; i < l; i++) {
                        int nnx = cp.x - i;
                        //범위를 벗어나면 경사로를 놓을 수 없음 / 값이 같지 않아도 놓을 수 없음 + 설치된 곳 설치할 수 없음
                        if(nnx >= n || nnx < 0 || board[cp.x][cp.y] != board[nnx][cp.y] || visited[nnx][cp.y]) {
                            flag = false;
                            break;
                        }
                    }
                    //경사로 설치 가능하면 바로 다음 지점으로 이동 + 경사로 설치한 좌표들 모두 방문처리
                    if(flag) {
                        q.offer(new Point(nx, cp.y));
                        //현재 지점 경사로 설치
                        visited[cp.x][cp.y] = true;
                        //경사로의 길이만큼 경사로 설치
                        for(int i = 1; i < l; i++) {
                            int nnx = cp.x - i;
                            visited[nnx][cp.y] = true;
                        }
                    }
                }
            }
        }
    }

    private class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}