로봇

📍 문제 설명

 

💡 접근

명령이 순차적으로 진행되는게 아니라 각각 진행됨에 유의를 해야한다.

해당 좌표에 방문했더라도 가리키고 있는 방향이 다를 수 있으니 이 문제에서도 3차원배열을 사용했다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, answer, cnt, max, min;
    static int startRobotX, startRobotY, startRobotDireciton, endRobotX, endRobotY, endRobotDireciton;
    static int Hx, Hy, Ex, Ey;
    static int[][] board, clone;
    static boolean[][][] visited;
    static int[][] dis;
    static boolean[][] successRoute;
    static int[] parent = new int[100001];
    static int[] ch, pm, combi, graph, go = {1,2,3};
    static boolean flag = false;
    static int[] dx = {0, 0, 1, -1}; //동서남북
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        board = new int[n+1][m+1];
        visited = new boolean[n+1][m+1][5];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //로봇의 출발 지점의 위치(행 열 방향)
        startRobotX = kb.nextInt();
        startRobotY = kb.nextInt();
        startRobotDireciton = kb.nextInt();
        //로봇의 도착 지점의 위치(행 열 방향)
        endRobotX = kb.nextInt();
        endRobotY = kb.nextInt();
        endRobotDireciton = kb.nextInt();
        T.solution();
    }

    private void solution() {
        Queue<Robot> q = new LinkedList<>();
        //로봇의 시작 위치 넣기
        q.add(new Robot(startRobotX, startRobotY, startRobotDireciton, 0));
        visited[startRobotX][startRobotY][startRobotDireciton] = true;

        while(!q.isEmpty()) {
            Robot cr = q.poll();
            //여기가 최단 거리이다.
            if(cr.x == endRobotX && cr.y == endRobotY && cr.direction == endRobotDireciton) {
                System.out.println(cr.cnt);
                return;
            }

            //현재 가리키는 방향을 구한다.
            //동쪽(1)이 들어오면 dx[0] 값 받기 위해
            int direction = cr.direction-1;

            //첫 지점에서 큐에 들어가야 하는것 - 해당 방향으로 전진, 해당 방향에서 왼쪽 오른쪽 회전

            //현재 가리키는 방향에서 1,2,3칸 움직인다.
            for(int i = 1; i <= 3; i++) {
                int nx = cr.x + i * dx[direction];
                int ny = cr.y + i * dy[direction];
                if(nx<1 || ny<1 || nx>n || ny>m || board[nx][ny] == 1) {
                    //그 다음것도 못가!
                    break;
                }

                if(!visited[nx][ny][cr.direction]) {
                    q.offer(new Robot(nx, ny, cr.direction, cr.cnt+1));
                }
            }

            //회전할 방향을 구한다.
            int[] rotate = directionRotate(cr.direction);
            //방문한 곳이어도 방향이 다르면 방문할 수 있어야한다. 여기도 3차원쓴다.

            //왼쪽 회전
            if(!visited[cr.x][cr.y][rotate[0]]) {
                q.offer(new Robot(cr.x, cr.y, rotate[0], cr.cnt + 1));
                visited[cr.x][cr.y][rotate[0]] = true;
            }
            //오른쪽 회전
            if(!visited[cr.x][cr.y][rotate[1]]) {
                q.offer(new Robot(cr.x, cr.y, rotate[1], cr.cnt + 1));
                visited[cr.x][cr.y][rotate[1]] = true;
            }

        }

    }

    //동쪽(1)에서 왼쪽회전-북쪽(4) 오른쪽회전-남쪽(3) +3 +2
    //서쪽(2)에서 왼쪽회전-남쪽(3) 오른쪽회전-북쪽(4) +1 +2
    //남쪽(3)에서 왼쪽회전-동쪽(1) 오른쪽회전-서쪽(2) -2 -1
    //북쪽(4)에서 왼쪽회전-서쪽(2) 오른쪽회전-동쪽(1) -2 -3
    private int[] directionRotate(int direction) {
        int[] rotate = new int[2];
        if(direction == 1) {
            rotate[0] = direction + 3;
            rotate[1] = direction + 2;
        }
        if(direction == 2) {
            rotate[0] = direction + 1;
            rotate[1] = direction + 2;
        }
        if(direction == 3) {
            rotate[0] = direction - 2;
            rotate[1] = direction - 1;
        }
        if(direction == 4) {
            rotate[0] = direction - 2;
            rotate[1] = direction - 3;
        }
        return rotate;
    }

    private class Robot {
        private int x;
        private int y;
        private int direction;
        private int cnt;

        public Robot(int x, int y, int direction, int cnt) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "[" + x + ", " + y + ", " + direction + ", " + cnt + "]";
        }
    }
}