Programmers - 블록 이동하기 with JAVA

 

 

 

로직

이 문제는 너무 복잡했다. 따라서 차분히 설계 후 코드를 작성하는 것이 훨씬 도움이 많이 됨을 느꼈다.

 

기본적으로 우선순위 큐와 방문처리 배열을 활용해 로직을 처리한다.

- 우선 순위 큐에은 비용, (x1, y1), (x2, y2), 방향을 담는다.

- 방문처리는 가로, 세로 둘 다 (x2, y2)를 기준으로 방문처리를 한다.

- 항상 가로는 왼쪽, 세로는 위쪽이 (x1, y1)이 되도록 고정 처리한다.

- 방향마다 모든 이동 경로에 대한 로직을 작성한다.

 

 

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] board) {
        int n = board.length;
        int m = board[0].length;
        // 비용, x1, y1, x2, y2, 방향
        // (x1, y1) = 가로에서는 왼쪽칸, 세로에서는 위쪽칸
        // 0 - 가로, 1- 세로
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        queue.add(Arrays.asList(0, 0, 0, 0, 1, 0));
        boolean[][][] visited = new boolean[n][m][2];
        while(queue.size() > 0){
            List<Integer> list = queue.poll();
            int cost = list.get(0);
            int x1 = list.get(1);
            int y1 = list.get(2);
            int x2 = list.get(3);
            int y2 = list.get(4);
            int direction = list.get(5);
            if(x2 == n-1 && y2 == m-1){
                return cost;
            }
            if(visited[x2][y2][direction]){
                continue;
            }
            visited[x2][y2][direction] = true;
            // 1. 가로
            if(direction == 0){
                // 방향 유지
                // 1-1. 오른쪽 이동
                if(y2+1 < m  && board[x2][y2+1] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1+1, x2, y2+1, 0));
                }
                // 1-2. 왼쪽 이동
                if(y1-1 >= 0 && board[x1][y1-1] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1-1, x2, y2-1, 0));
                }
                // 1-3. 위쪽 이동
                if(x1-1 >= 0&& board[x1-1][y1] != 1 && board[x2-1][y2] != 1){
                    queue.add(Arrays.asList(cost+1, x1-1, y1, x2-1, y2, 0));
                }
                // 1-4. 아래쪽 이동 
                if(x1+1 < n && board[x1+1][y1] != 1 && board[x2+1][y2] != 1){
                    queue.add(Arrays.asList(cost+1, x1+1, y1, x2+1, y2, 0));
                }
                
                
                // 방향 변경
                // 1-5. 유지-위왼 이동
                if(x2-1 >= 0 && y2-1 >=0 && board[x2-1][y2-1] != 1 
                  && board[x2-1][y2] != 1){
                    queue.add(Arrays.asList(cost+1, x2-1, y2-1, x1, y1, 1));
                }
                // 1-6. 위오-유지 이동
                if(x1-1 >= 0 && y1+1 < m && board[x1-1][y1+1] != 1
                  && board[x1-1][y1] != 1){
                    queue.add(Arrays.asList(cost+1, x1-1, y1+1, x2, y2, 1));
                }
                // 1-7. 유지-아래왼 이동
                if(x2+1 < n && y2-1 >=0 && board[x2+1][y2-1] != 1 
                  && board[x2+1][y2] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1, x2+1, y2-1, 1));
                }
                // 1-8. 아래오, 유지 이동
                if(x1+1 < n && y1+1 < m && board[x1+1][y1+1] != 1
                  && board[x1+1][y1] != 1){
                    queue.add(Arrays.asList(cost+1, x2, y2, x1+1, y1+1, 1));
                }
            }
            // 2. 세로
            if(direction == 1){
                // 방향 유지
                // 2-1. 오른쪽 이동
                if(y1+1 < m && board[x1][y1+1] != 1 && board[x2][y2+1] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1+1, x2, y2+1, 1));
                }
                // 2-2. 왼쪽 이동
                if(y1-1>= 0 && board[x1][y2-1] != 1 && board[x2][y2-1] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1-1, x2, y2-1, 1));
                }
                // 2-3. 위쪽 이동
                if(x1-1 >= 0 && board[x1-1][y1] != 1){
                    queue.add(Arrays.asList(cost+1, x1-1, y1, x2-1, y2, 1));
                }
                // 2-4. 아래쪽 이동
                if(x2+1 < n && board[x2+1][y2] != 1){
                    queue.add(Arrays.asList(cost+1, x1+1, y1, x2+1, y2, 1));
                }
                
                // 방향 변경
                // 2-5. 유지-오위 이동
                if(x2-1 >= 0 && y2+1 < m && board[x2-1][y2+1] != 1
                  && board[x2][y2+1] != 1){
                    queue.add(Arrays.asList(cost+1, x1, y1, x2-1, y2+1, 0));
                }
                // 2-6. 오아-유지 이동
                if(x1+1 < n && y1+1 < m && board[x1+1][y1+1] != 1
                  && board[x1][y1+1] != 1){
                    queue.add(Arrays.asList(cost+1, x2, y2, x1+1, y1+1, 0));
                }
                // 2-7. 유지-왼위 이동
                if(x2-1 >= 0 && y2-1 >= 0 && board[x2-1][y2-1] != 1
                  && board[x2][y2-1] != 1){
                    queue.add(Arrays.asList(cost+1, x2-1, y2-1, x1, y1, 0));
                }
                // 2-8. 왼아, 유지 이동
                if(x1+1 < n && y1-1 >= 0 && board[x1+1][y1-1] != 1
                  && board[x1][y1-1] != 1){
                    queue.add(Arrays.asList(cost+1, x1+1, y1-1, x2, y2, 0));
                }
            }
        }
        return -1;
    }
}