블록 이동하기

문제

https://programmers.co.kr/learn/courses/30/lessons/60063

코드

import java.util.*;

class Solution {

    int mv[][] = {
        {-1,0},
        {0,1},
        {1,0},
        {0,-1}
    };
    int spin[][] = {
        {-1,0},
        {-1,1},
        {0,1},
        {1,1},
        {1,0},
        {1,-1},
        {0,-1},
        {-1,-1}
    };


    class Node implements Comparable<Node>{
        int row;
        int col;
        public Node(int row, int col){
            this.row = row;
            this.col = col;
        }

        @Override
        public int compareTo(Node obj){
            if(this.row < obj.row){
                return -1;
            }else if(this.row > obj.row){
                return 1;
            }else{
                if(this.col < obj.col){
                    return -1;
                }else if(this.col > obj.col){
                    return 1;
                }else{
                    return 0;
                }
            }
        }

        @Override
        public String toString(){
            return "{ row : " + this.row 
                + ", col : " + this.col + "}";
        }

        public boolean equals(Node obj){
            if(this.row == obj.row && this.col == obj.col)
                return true;
            else
                return false;
        }
    }

    class Drone{
        int depth;
        int dir;
        ArrayList<Node> points;
        public Drone(int depth, int dir, ArrayList<Node> points){
            this.depth = depth;
            this.dir = dir;
            this.points = points;
        }
    }


    void checkHis(boolean his[][][][], ArrayList<Node> points){
        his[points.get(0).row][points.get(0).col][points.get(1).row][points.get(1).col] = true;

    }

    boolean isAns(Drone drone, Node end){
        for(Node point : drone.points)
            if(point.row == end.row && point.col == end.col)
                return true;
        return false;
    }

    boolean isValid(int board[][], ArrayList<Node> points){
        int N = board.length;
        for(Node point : points){
            if(N <= point.row || point.row < 0 || N <= point.col || point.col < 0)
                return false;
            if(board[point.row][point.col] == 1)
                return false;
        }
        return true;
    }

    boolean isVisit(boolean his[][][][], ArrayList<Node> list){
        if(his[list.get(0).row][list.get(0).col][list.get(1).row][list.get(1).col])
            return true;
        else
            return false;
    }

    int findDir(ArrayList<Node> list){
        int tmp_arr[] = {list.get(1).row - list.get(0).row, list.get(1).col - list.get(0).col};
        for(int i=0; i<8; i++)
            if(spin[i][0] == tmp_arr[0] && spin[i][1] == tmp_arr[1])
                return i;
        return -1;
    }



    public int solution(int[][] board) {
        int answer = -1;
        Node end = new Node(board.length-1, board.length-1);
        Queue<Drone> q = new LinkedList();
        boolean his[][][][] = new boolean[board.length][board.length][board.length][board.length];
        ArrayList<Node> tmp = new ArrayList<Node>();
        tmp.add(new Node(0,1)); tmp.add(new Node(0,0));
        Collections.sort(tmp);
        checkHis(his, tmp);
        Drone sd = new Drone(0, 2, tmp);
        q.add(sd);
        while(!q.isEmpty()){
            Drone cur_drone = q.poll();
            if(isAns(cur_drone, end)){
                return cur_drone.depth;
            }

            int c_dir = cur_drone.dir;
            ArrayList<Node> c_p = cur_drone.points;
            int c_dep = cur_drone.depth;

//             System.out.print(c_dep + " : ");
//             for(Node p : c_p)
//                 System.out.print(p + " ");
//             System.out.println();

            //움직이기
            for(int i=0; i<4; i++){
                ArrayList<Node> n_l = new ArrayList<>();
                for(Node point : c_p){
                    n_l.add(new Node(point.row+mv[i][0], point.col+mv[i][1]));
                }
                Collections.sort(n_l);
                if(!isValid(board, n_l))
                    continue;
                if(isVisit(his, n_l))
                    continue;
                checkHis(his, n_l);
                q.add(new Drone(c_dep+1, c_dir, n_l));

            }

            int[] offset = {0, 4};
            // 90도 회전
            for(int i=0; i<2; i++){
                Node s_n = c_p.get(i);
                int tmp_dir = (c_dir+offset[i])%8;
                ArrayList<Node> pred = new ArrayList<>();
                for(int j=1; j<=2; j++){
                    int n_r = s_n.row + spin[(tmp_dir+j)%8][0];
                    int n_c = s_n.col + spin[(tmp_dir+j)%8][1];
                    pred.add(new Node(n_r, n_c));
                }
                if(isValid(board, pred)){
                    Node n1 = new Node(s_n.row, s_n.col);
                    Node n2 = new Node(pred.get(1).row, pred.get(1).col);
                    ArrayList<Node> n_l = new ArrayList<>();
                    n_l.add(n1); n_l.add(n2);
                    Collections.sort(n_l);
                    if(!isVisit(his, n_l)){
                        checkHis(his, n_l);    
                        // q.add(new Drone(c_dep+1, (tmp_dir+2)%8, n_l));
                        q.add(new Drone(c_dep+1, findDir(n_l), n_l));

                    }
                }
            }
            // -90도 회전
            for(int i=0; i<2; i++){
                Node s_n = c_p.get(i);
                int tmp_dir = (c_dir+offset[i])%8;
                ArrayList<Node> pred = new ArrayList<>();
                for(int j=1; j<=2; j++){
                    int n_r = s_n.row + spin[(tmp_dir-j+8)%8][0];
                    int n_c = s_n.col + spin[(tmp_dir-j+8)%8][1];
                    pred.add(new Node(n_r, n_c));
                }
                if(isValid(board, pred)){
                    Node n1 = new Node(s_n.row, s_n.col);
                    Node n2 = new Node(pred.get(1).row, pred.get(1).col);
                    ArrayList<Node> n_l = new ArrayList<>();
                    n_l.add(n1); n_l.add(n2);
                    Collections.sort(n_l);
                    if(!isVisit(his, n_l)){
                        checkHis(his, n_l);    
                        // q.add(new Drone(c_dep+1, (tmp_dir+6)%8, n_l));
                        q.add(new Drone(c_dep+1, findDir(n_l), n_l));

                    }
                }
            }
        }
        return answer;
    }
}

피드백

• 한 번 못풀었다가 다시 푼 문제이다.
• 전에 못 푼 이유는 his를 어떻게 제대로 구성하는지 몰라서이다.
  • 결국에 첫 번째 점 row, col 과 두 번째 점 row, col 방문 기록인 his[f.row][f.col][s.row][s.col] 으로 설계했다.
    • 첫 번째 좌표와 && 두 번째 좌표 방문 여부를 저장한다.
  • 문제는his[first][second] 와 his[second][first]가 중복이 된다는 점이다.
    • 생각을 해보면, 두 점은 순서가 상관없는 집합이다. 즉 조합처럼 임의의 순서를 우리가 그냥 정해서 경우의 수를 구해줄 수가 있다.
    • 나는 점 두 개 간 우선순위를 정하여 첫 번째 점, 두 번째 점이 정렬되도록 짯다.
    • 그럼 두 개의 경우가 하나의 경우로 통일된다.
• his설계를 다하고, 드론을 Queue에 넣어 일반적인 bfs처럼 푼다.
  • his[f.row][f.col][s.row][s.col] 식으로 중복체크를 하면 일반적인 bfs 푸는 것 마냥 풀 수 있다.
  • 드론은 dir을 넣어서 회전 구현을 좀 더 쉽게 했다.
• 하지만 회전의 경우는 구현이 쉽지는 않았다.
  • 두 점을 각각 기준점으로 잡고 90도 회전, -90도 회전하는 경우를 계산하였다.
  • 회전이 일어나면서 두 점간이 이루는 방향도 변화가 되지만, 점 간의 우선순위에 의하여 왼쪽에서 오른쪽, 위에서 아래 두 경우의 방향만이 존재한다.
  • 이 두 방향만으로 두 점간의 방향이 변하도록 방향 전환을 처리했다.
• 접근하는 아이디어는 단순했으나, 구현 방법과 his[][][][] 를 설계하도록 접근하는 것이 어려웠던 문제였다.