22.블록 이동하기

📍 문제 설명

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

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

 

💡 접근

최단거리 미로찾기 같은 문제였는데 로봇이 2 X 1의 크기라는 것이 변수였다.

미로 찾기 문제와는 달리 해당 좌표의 방문체크를 하는 배열이 아닌 리스트가 필요했다.

현재 위치에서 상하좌우, 로봇이 가로로 있을 때의 회전, 세로로 있을 때의 회전 각각 다르게 처리해줬어야했다.

이동할 수 있는 위치에 대해서 방문 좌표 리스트를 확인해서 방문 가능한 곳이라면 큐에 넣고 방문처리를 해주면 됐다.

출력은 2칸 중 1칸이라도 좌표가 n,n이면 도착한 것으로 처리해줄 수 있었다.

 

 

👩‍💻 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[][] board = {
                {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}
        };

        solution(board);

    }

    private static int solution(int[][] board) {
        int answer = 0;

        int n = board.length;
        int[][] newBoard = new int[n+2][n+2];
        //지도 늘리기
        for (int i = 0; i < n + 2; i++) {
            for (int j = 0; j < n + 2; j++) {
                newBoard[i][j] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newBoard[i + 1][j + 1] = board[i][j];
            }
        }

        Queue<Node> q = new LinkedList<>();
        ArrayList<Node> visited = new ArrayList<>();
        //시작 위치 설정 (1,1) (1,2) 이고 거리는 0
        Node pos = new Node(1, 1, 1, 2, 0);
        //해당 위치 큐에 삽입
        q.offer(pos);
        //해당 위치 방문 처리
        visited.add(pos);

        while(!q.isEmpty()) {
            pos = q.poll();
            // (n,n)에 도착했으면 최단 거리이므로 바로 반환
            if((pos.pos1X == n && pos.pos1Y == n) || (pos.pos2X == n && pos.pos2Y == n)) {
                System.out.println(pos.distance);
                return pos.distance;
            }
            
            //현재 위치에서 이동할 수 있는 위치들 확인
            ArrayList<Node> nextPos = getNextPos(pos, newBoard);
            for(int i = 0; i < nextPos.size(); i++) {
                //방문 하지 않았으면 큐에 넣고 방문처리
                boolean check = true;
                pos = nextPos.get(i);
                for (int j = 0; j < visited.size(); j++) {
                    //방문체크 리스트를 통해서 방문 확인
                    if (pos.pos1X == visited.get(j).pos1X && pos.pos1Y == visited.get(j).pos1Y && pos.pos2X == visited.get(j).pos2X && pos.pos2Y == visited.get(j).pos2Y) {
                        check = false;
                        break;
                    }
                }
                if(check) {
                    q.offer(pos);
                    visited.add(pos);
                }
            }
        }
        return answer;
    }

    public static ArrayList<Node> getNextPos(Node pos, int[][] board) {
        // 반환 결과(이동 가능한 위치들)
        ArrayList<Node> nextPos = new ArrayList<Node>();
        // (상, 하, 좌, 우)로 이동하는 경우에 대해서 처리
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int pos1NextX = pos.pos1X + dx[i];
            int pos1NextY = pos.pos1Y + dy[i];
            int pos2NextX = pos.pos2X + dx[i];
            int pos2NextY = pos.pos2Y + dy[i];
            int distanceNext = pos.distance + 1;
            // 이동하고자 하는 두 칸이 모두 비어 있다면
            if (board[pos1NextX][pos1NextY] == 0 && board[pos2NextX][pos2NextY] == 0) {
                nextPos.add(new Node(pos1NextX, pos1NextY, pos2NextX, pos2NextY, distanceNext));
            }
        }
        // 현재 로봇이 가로로 놓여 있는 경우
        int[] hor = {-1, 1};
        if (pos.pos1X == pos.pos2X) {
            for (int i = 0; i < 2; i++) { // 위쪽으로 회전하거나, 아래쪽으로 회전
                // 위쪽 혹은 아래쪽 두 칸이 모두 비어 있다면
                if (board[pos.pos1X + hor[i]][pos.pos1Y] == 0 && board[pos.pos2X + hor[i]][pos.pos2Y] == 0) {
                    nextPos.add(new Node(pos.pos1X, pos.pos1Y, pos.pos1X + hor[i], pos.pos1Y, pos.distance + 1));
                    nextPos.add(new Node(pos.pos2X, pos.pos2Y, pos.pos2X + hor[i], pos.pos2Y, pos.distance + 1));
                }
            }
        }
        // 현재 로봇이 세로로 놓여 있는 경우
        int[] ver = {-1, 1};
        if (pos.pos1Y == pos.pos2Y) {
            for (int i = 0; i < 2; i++) { // 왼쪽으로 회전하거나, 오른쪽으로 회전
                // 왼쪽 혹은 오른쪽 두 칸이 모두 비어 있다면
                if (board[pos.pos1X][pos.pos1Y + ver[i]] == 0 && board[pos.pos2X][pos.pos2Y + ver[i]] == 0) {
                    nextPos.add(new Node(pos.pos1X, pos.pos1Y, pos.pos1X, pos.pos1Y + ver[i], pos.distance + 1));
                    nextPos.add(new Node(pos.pos2X, pos.pos2Y, pos.pos2X, pos.pos2Y + ver[i], pos.distance + 1));
                }
            }
        }
        // 현재 위치에서 이동할 수 있는 위치를 반환
        return nextPos;
    }

    private static class Node {
        private int pos1X;
        private int pos1Y;
        private int pos2X;
        private int pos2Y;
        private int distance;

        public Node(int pos1X, int pos1Y, int pos2X, int pos2Y,int distance) {
            this.pos1X = pos1X;
            this.pos1Y = pos1Y;
            this.pos2X = pos2X;
            this.pos2Y = pos2Y;
            this.distance = distance;
        }

    }
}