Programmers[60063] - 블록_이동하기[Level3]

링크

코딩테스트 연습 - 블록 이동하기

문제설명

• 깊이&너비 우선탐색 + 시뮬

문제풀이

• 상하좌우 이동말고 축 기준으로 돌리면서 이동가능한 경로 탐색 문제이다.
• 2칸을 차지하는 것을 기억하기위해서 중간 지점을 visited로 관리한다.
• BFS로 탐색했다. visit 처리해서 DFS도 될듯.

문제코드

package programmers;

import java.util.LinkedList;


public class Solution60063_블록_이동하기 {

    public static int[][] dir = {
            {-1,0},
            {0,1},
            {1,0},
            {0,-1},
    };

    public static int N;

    public static boolean[][] visited;

    public static boolean inline(int r, int c) {
        return (r>=0 && r<N && c>=0 && c<N);
    }

    public static boolean inline_mat(int[][] next) {
        return (next[0][0]>=0 && next[0][0]<N && next[0][1]>=0 && next[0][1]<N &&
                next[1][0]>=0 && next[1][0]<N && next[1][1]>=0 && next[1][1]<N);
    }

    public static int solution(int[][] board) {
        N = board.length;

//        (0,0)-(0,1) or (0,1)-(0,0) == (0,0.5) 로 표현가능 *2해서 배열에 넣어놓기
        visited = new boolean[N*2][N*2];

        int answer = 0;

        LinkedList<int[][]> q = new LinkedList<int[][]>();

        q.add(new int[][] {{0,0},{0,1}});
        visited[0+0][0+1]=true;
        int[][] now;
        int[][] next = new int[2][2];

        top:
        while(!q.isEmpty()) {

            for (int i = 0, qsize = q.size(); i < qsize; i++) {
                now = q.poll();
//                도착했으면
                if((now[0][0]==N-1 && now[0][1]==N-1) || (now[1][0]==N-1 && now[1][1]==N-1)) {
//                    System.out.println("found answer");
                    break top;
                }
//                상하좌우이동
                for (int d = 0; d < 4; d++) {
                    for (int j = 0; j < 2; j++) {
                        next[j][0] = now[j][0]+dir[d][0];
                        next[j][1] = now[j][1]+dir[d][1];

                    }
//                    경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next)&&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }
                }
//                대각선이동 (이동하는칸에 1이 없어야 함)
//                가로로 누워있는 경우
                if(now[0][1]-now[1][1]==-1) {
//                    왼쪽기준
//                    왼쪽위 이동, 오른쪽위 비어야함
                    next = new int[][] {
                            {now[0][0]-1,now[0][1]},
                            {now[0][0],now[0][1]},
                    };
//                    오른쪽 위가 비어야함(경계검사도해야함->안해도됨 next경계검사먼저하면) && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next) &&
                        board[now[0][0]-1][now[0][1]+1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }                        
//                    왼쪽밑 이동, 오른쪽밑 비어야함
                    next = new int[][] {
                        {now[0][0],now[0][1]},
                        {now[0][0]+1,now[0][1]},
                    };
//                    오른쪽 밑이 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next)&&
                        board[now[0][0]+1][now[0][1]+1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }
//                    오른쪽기준
//                    오른쪽위 이동, 왼쪽위 비어야함
                    next = new int[][] {
                        {now[1][0]-1,now[1][1]},
                        {now[1][0],now[1][1]},
                    };
//                    왼쪽 위가 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next)&&
                        board[now[0][0]-1][now[0][1]]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }            
//                    오른쪽밑 이동, 왼쪽밑 비어야함
                    next = new int[][] {
                        {now[1][0],now[1][1]},
                        {now[1][0]+1,now[1][1]},
                    };
//                    왼쪽 밑이 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next) &&
                        board[now[0][0]+1][now[0][1]]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }            
                }

//                세로로 누워있는 경우
                else {
//                    위기준
//                    왼쪽 이동, 왼쪽아래 비어야함
                    next = new int[][] {
                            {now[0][0],now[0][1]-1},
                            {now[0][0],now[0][1]},
                    };
//                    왼쪽아래가 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next) &&
                        board[now[0][0]+1][now[0][1]-1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }                        
//                    오른쪽 이동, 오른쪽밑 비어야함
                    next = new int[][] {
                        {now[0][0],now[0][1]},
                        {now[0][0],now[0][1]+1},
                    };
//                    오른쪽 밑이 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next)&&
                        board[now[0][0]+1][now[0][1]+1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }
//                    아래기준
//                    왼쪽 이동, 왼쪽위 비어야함
                    next = new int[][] {
                        {now[1][0],now[1][1]-1},
                        {now[1][0],now[1][1]},
                    };
//                    왼쪽 위가 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next)&&
                        board[now[0][0]][now[0][1]-1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }            
//                    오른쪽 이동, 오른쪽위 비어야함
                    next = new int[][] {
                        {now[1][0],now[1][1]},
                        {now[1][0],now[1][1]+1},
                    };
//                    오른쪽위 비어야함 && 경계검사 && 벽이 아니고 && visit check
                    if(    inline_mat(next) &&
                        board[now[0][0]][now[0][1]+1]==0 &&
                        board[next[0][0]][next[0][1]]==0 && board[next[1][0]][next[1][1]]==0 &&
                        !visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]
                        ){
                        q.add(new int[][] {{next[0][0],next[0][1]},{next[1][0],next[1][1]}});
                        visited[next[0][0]+next[1][0]][next[1][0]+next[1][1]]=true;
                    }            
                }


            }
            answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[][] {{0, 0, 0, 1, 1}
                                                ,{0, 0, 0, 1, 0}
                                                ,{0, 1, 0, 1, 1}
                                                ,{1, 1, 0, 0, 1}
                                                ,{0, 0, 0, 0, 0}}));
    }
}

아쉬운 점

• Eclipse에서 디버깅을 하기위해서 Programmers가 주는대로 public int solution()을 쓰기위해 public void main()로하면 class를 인식을 할 수 없음
  • public static void main(){}써야 함
• 경계검사하는 함수를 많이 써야 하는 문제임, 특히 한 좌표가 아니라 좌표 2개를 모두 검사해야했기 때문에 inline check하는 함수를 모듈화해서 미리 써놓는게 더 깔끔했음.
• 경계검사를 먼저해야 축 이동할 때 걸치는 칸 검사할 때 인덱스 오류가 안뜸.
• Queue에 next[][]를 넣으면 next 주소값이 들어가기 때문에 new int[][]{}선언 해주고 넣어야 함. next.clone()도 안되던데?

잘한 점

• O(N) = 중간선분의 갯수이므로 BFS(<100*100) 임
• 조건은 꼼꼼하게 다 따졌음(축 이동할 때, 벽에 걸치면 안되는거)
• 가로로 누웠을 경우, 세로로 누웠을 경우 회전 경우의 수 꼼꼼하게 처리했음.
• 2개의 칸을 차지하는 경우가 2가지가 나오는데 하나로 처리할 수 있게 visit 처리를 했음
  • (0,0)-(0,1) == (0,1)-(0,0) 인데 가운데 중간 선분을 저장할 수 있으면 하나로 처리 가능함
  • ((0+0)/2,(0+1)/2) = (0,0.5) 이렇게.
  • 배열인덱스는 정수만 가능하기에 그냥 두개 더한 값을 visit에 저장해놓음
• 2개의 칸 처리를 할 때, 애초에 하나의 경우만 만들게 queue에 정렬해서 넣어주면 됨.
  • 그래서 next[][]배열을 만들 때, 좌->우, 상->하 순서로 정렬된 을 만들어서 처리해줌.
  • visit처리를 할 때, 두 좌표의 정보를 가진 100*100*100*100 배열 써도 됐을듯, 근데 굳이 안쓰는게 더 낫긴한듯.
    • hashset + 객체 사용해도 됐을듯, 개인적으로 디버깅할 때 객체쓰면 힘들어서 안씀
• 좀 빡셌지만 1:20
  • 카카오코테인데 더 빨리 풀어야했나

next배열 만들 때