[프로그래머스] 카카오_블록 이동하기 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/60063?language=java 

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

 

풀이

나는 이 문제를 조금 복잡하게 푼 것 같다.

 

우선 Robot 클래스를 만들어서 x좌표와 y좌표, 현재 방향(0은 가로 1은 세로), 걸린 시간을 저장하게 만들었다. 

참고로 방향이 가로일 때 x, y는 왼쪽 좌표 기준, 세로일 때 x, y는 위쪽 좌표를 기준으로 한 것이다.

 

이후 탐색은 BFS를 통해서 모든 경우의 수를 따지면 된다.

이때 상하좌우로 움직이는 경우의 수+회전 4방향 경우의 수를 모두 계산해줘야 한다.

또한, 상하좌우로 움직일 수 있는지, 회전 시킬 수 있는지 체크해야 하는데 나는 이것을 하나의 함수로 해결했다.

 

회전을 할 수 있다는 것은 생각해보면 회전 하기 전 상태 그대로 움직일 수 있는지 체크하는 것과 같다. 

따라서 움직일 수 있는지 체크하는 함수 하나로 해결했다.

 

자세한 내용은 코드를 참고하자.

 

 

import java.util.*;
 
class Solution {
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    static int rx[][] = {{-1,0,-1,0}, {0,0,1,1} }; 
    static int ry[][] = {{0,0,1,1}, {-1,0,-1,0}};
    
    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        int len = board.length;
        Queue<Robot> q = new LinkedList<>();
        boolean visited[][][] = new boolean[2][101][101];
                
        q.add(new Robot(0,0,0,0));
        visited[0][0][0] = true;
        
        while(!q.isEmpty()){
            Robot cur = q.poll();
            if(cur.dir == 0 && cur.x == len-1 && cur.y == len-2 ){
                answer = Math.min(answer, cur.cnt);
                continue;
            }else if(cur.dir == 1 && cur.x==len-2 && cur.y == len-1){
                answer = Math.min(answer, cur.cnt);
                continue;
            }
            
            // 상하좌우 이동
            for(int i=0; i<4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                /* 움직일 수 있는지 체크 */
                if(!canMove(nx,ny, cur.dir, board)) continue;
                
                if(!visited[cur.dir][nx][ny]){
                    q.add(new Robot(nx,ny,cur.dir, cur.cnt+1));
                    visited[cur.dir][nx][ny] = true;
                }
            }
            
            // 회전
            for(int i=0; i<4; i++){
                int nx = cur.x + rx[cur.dir][i];
                int ny = cur.y + ry[cur.dir][i];
                
                /* 가로 방향은 상하로 움직일 수 있으면 회전 가능 */
                int cx = cur.x + dx[i%2];
                int cy = cur.y + dy[i%2];
                
                if(cur.dir == 1){   // 세로 방향은 좌우로 움직일 수 있으면 회전 가능
                    cx = cur.x + dx[i<2?i+2:i];
                    cy = cur.y + dy[i<2?i+2:i];
                }
                
                int ndir = cur.dir^1;   // 방향 XOR 연산으로 계산
                
                /* 회전 할 수 있는지 체크 */
                if(!canMove(nx,ny, ndir, board)|| !canMove(cx, cy, cur.dir, board) ) continue;
                
                if(!visited[ndir][nx][ny]){
                    q.add(new Robot(nx,ny,ndir,cur.cnt+1));
                    visited[ndir][nx][ny] = true;
                }
            }
        }
        
        return answer;
    }
    
    /* 움직일 수 있는지 체크 */
    public static boolean canMove(int nx, int ny, int dir, int[][] board){
        int len = board.length;
        if(dir == 0){
            if(nx<0 || ny <0 || nx >= len || ny >= len || 
               ny+1 >= len ||board[nx][ny] != 0 || board[nx][ny+1] != 0 ){
                return false;
            }
            return true;
        }else{
            if(nx<0 || ny<0 || nx >= len || nx+1>=len || ny>=len ||
              board[nx][ny] != 0 || board[nx+1][ny] != 0){
                return false;
            }
            return true;
        }
    }
        
    
    static class Robot{
        int x;
        int y;
        int dir;    // 0:가로 1:세로
        int cnt;    // 걸린 시간
        Robot(int x, int y, int dir, int cnt){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cnt = cnt;
        }
    }
}