2020 KAKAO BLIND RECRUITMENT : 블록 이동하기 😰 (문제 미침)

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

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

// 코드

import java.util.*;
 
class Solution {
    
    // 좌표정보를 관리하는 클래스
    class Point {
        // 행, 열, 방향, 시간
        int row, col, dir, time;
        Point(int row, int col, int dir, int time) {
            this.row = row;
            this.col = col;
            this.dir = dir;
            this.time = time;
        }
    }
    
    // 드론의 방향 : 시계방향으로..
    static final int UP    = 0;
    static final int RIGHT = 1;
    static final int DOWN  = 2;
    static final int LEFT  = 3;
    
    // 상, 하, 좌, 우
    int[][] Deltas       = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    // 0 시계, 1 반시계 돌림..
    int[][][] RotateDeltas = {
        { {1, 1},  {1, -1},  {-1, -1}, {-1, 1} },
        { {1, -1}, {-1, -1}, {-1, 1},  {1, 1} }
    };  
    
    int[][][] CornerDeltas = {
        { {-1, 1},  {1, 1},  {1, -1}, {-1, -1} },
        { {-1, -1}, {-1, 1}, {1, 1},  {1, -1} }
    };  
    
    // 일반 멤버 변수
    int N;    
    int[][] Board;    
    Deque<Point[]> DEQ = new ArrayDeque<>();
    boolean[][][] Visited = new boolean[100][100][4];     
    
    boolean isValid(Point[] pt) {
        
        for(int i = 0; i < 2; ++i) {
            // 범위를 벗어나는 경우
            if(pt[i].row < 0 || pt[i].row > N-1 || pt[i].col < 0 || pt[i].col > N-1) return false;
            // 벽인경우
            if(Board[pt[i].row][pt[i].col] == 1) return false;
            // 방문한경우
            if(Visited[pt[i].row][pt[i].col][pt[i].dir]) return false;
        }
        return true;
    }
    
    // 파라미터 정보 : (현재 위치 정보, 시계방향인지 반시계방향인지, 회전축)
    int rotate(Point[] curr, int ccw, int idx) {
        
        Point[] newPt = new Point[2];
        
        // a회전축
        int a = idx, b = (idx + 1) % 2;
        int dir = curr[a].dir;
        
        // 시계방향 1, 반시계방향 3
        newPt[0] = new Point(
            curr[a].row, 
            curr[a].col, 
            ((curr[a].dir + (ccw == 0 ? 1 : 3)) % 4), 
            (curr[a].time + 1)
        );
        
        // 회전축이 아닌 나머지칸 즉 b를 기준으로 이동
        newPt[1] = new Point(
            curr[b].row + RotateDeltas[ccw][dir][0], 
            curr[b].col + RotateDeltas[ccw][dir][1], 
            ((curr[b].dir + (ccw == 0 ? 1 : 3)) % 4),
            (curr[a].time + 1)
        );
        
        // 회전 불가능한 경우
        if(!isValid(newPt)) return 0;
        if(Board[ curr[a].row + CornerDeltas[ccw][dir][0] ][ curr[a].col + CornerDeltas[ccw][dir][1] ] == 1) return 0;
        
        for(int i = 0; i < 2; ++i) {
            // 목적지 도달
            if(newPt[0].row == N - 1 && newPt[0].col == N - 1) return newPt[i].time;
            Visited[newPt[i].row][newPt[i].col][newPt[i].dir] = true;            
        }
        
        DEQ.add( new Point[]{ newPt[0], newPt[1]} );
        return 0;
    }
    
    // 메인 클래스
    public int solution(int[][] board) {
        
        Board = board;
        N     = board.length;
        
        DEQ.add( new Point[]{ new Point(0, 0, RIGHT, 0), new Point(0, 1, LEFT, 0) } );
        Visited[0][0][RIGHT] = true;
        Visited[0][1][LEFT]  = true;
        
        Point[] curr  = new Point[2];
        Point[] newPt = new Point[2];
         
        while( (curr = DEQ.poll()) != null ) {
            
            for(int j = 0; j < 4; ++j) { // 4방 탐색
                for(int i = 0; i < 2; ++i) { // 이동할 곳 : 두 개의 새로운 좌표를 만들어낸다.
                    newPt[i] = new Point( (curr[i].row + Deltas[j][0]), (curr[i].col + Deltas[j][1]), curr[i].dir, (curr[i].time + 1));
                }
                
                // 유효한 경우만 추가
                if(!isValid(newPt)) continue;
                
                for(int i = 0; i < 2; ++i) {
                    // 목적지 도착 확인
                    if(newPt[i].row == N-1 && newPt[i].col == N-1) return newPt[i].time;
                    Visited[newPt[i].row][newPt[i].col][newPt[i].dir] = true;
                }
                
                DEQ.add(new Point[]{ newPt[0], newPt[1] }); 
            }
            
            // 회전 : 시계방향 0(ccw), 반시계방향 1(ccw)
            for(int ccw = 0; ccw < 2; ++ccw) {
                for(int i = 0; i < 2; ++i) {
                    // i = 0 이면 첫 번째칸을 축으로 회전
                    // i = 1 이면 두 번째칸을 축으로 회전
                    int ret = rotate(curr, ccw, i);
                    if(ret != 0 ) return ret;                    
                }
            }
            
        }
        
        // 문제조건상 이곳은 오지 못함.
        // 아무값이나 반환
        return 0;
    }
}