[백준] 로봇

[yu-heejin]

https://www.acmicpc.net/problem/1726

[yu-heejin]

import java.io.*;
import java.util.*;

public class Main {
    // 우좌하상
    static final int[] MOVE_X = {0, 0, 1, -1};
    static final int[] MOVE_Y = {1, -1, 0, 0};

    static int[][] board;
    static int m, n;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);

        board = new int[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                board[i + 1][j + 1] = Integer.parseInt(input[j]);
            }
        }

        // 로봇의 출발 지점 - 행, 열, 바라보는 방향
        int[] robot = new int[4];
        input = br.readLine().split(" ");

        for (int i = 0; i < 3; i++) {
            robot[i] = Integer.parseInt(input[i]);
        }

        robot[3] = 0;    // 명령어의 개수

        // 로봇의 도착 지점
        int[] goal = new int[3];
        input = br.readLine().split(" ");

        for (int i = 0; i < 3; i++) {
            goal[i] = Integer.parseInt(input[i]);
        }

        System.out.println(bfs(robot, goal));
    }

    private static int bfs(int[] robot, int[] goal) {
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[m + 1][n + 1][5];

        q.add(robot);
        visited[robot[0]][robot[1]][robot[2]] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();

            // 만약 목표에 도달한 경우 반복을 종료한다.
            if (curr[0] == goal[0] && curr[1] == goal[1] && curr[2] == goal[2]) {
                return curr[3];
            }

            // Go: 현재 바라보는 방향으로 전진하는 경우
            for (int k = 1; k <= 3; k++) {
                int[] next = getNextMove(curr, k);

                if (!canMove(next)) continue;
                if (visited[next[0]][next[1]][next[2]]) continue;

                // Go만 진행하는 경우
                q.add(next);
                visited[next[0]][next[1]][next[2]] = true;

                // Go 하고 Turn하는 경우
                for (int dir = 0; dir < 2; dir++) {
                    int[] addTurn = getNextTurn(next, dir);

                    if (!canMove(addTurn)) continue;
                    if (visited[addTurn[0]][addTurn[1]][addTurn[2]]) continue;

                    q.add(addTurn);
                    visited[addTurn[0]][addTurn[1]][addTurn[2]] = true;
                }
            }

            // Turn: 회전
            for (int dir = 0; dir < 2; dir++) {
                int[] next = getNextTurn(curr, dir);

                if (!canMove(next)) continue;
                if (visited[next[0]][next[1]][next[2]]) continue;

                // Turn만 진행하는 경우
                q.add(next);
                visited[next[0]][next[1]][next[2]] = true;

                // Turn하고 Go하는 경우
                for (int k = 1; k <= 3; k++) {
                    int[] addMove = getNextMove(next, k);

                    if (!canMove(addMove)) continue;
                    if (visited[addMove[0]][addMove[1]][addMove[2]]) continue;

                    q.add(addMove);
                    visited[addMove[0]][addMove[1]][addMove[2]] = true;
                }
            }
        }

        return -1;
    }

    // Go
    private static int[] getNextMove(int[] curr, int k) {
        switch (curr[2]) {
            case 1:
                // 동쪽인 경우 - 오른쪽으로 이동
                return new int[] {curr[0], curr[1] + k, curr[2], curr[3] + 1};
            case 2:
                // 왼쪽
                return new int[] {curr[0], curr[1] - k, curr[2], curr[3] + 1};
            case 3:
                // 아래쪽
                return new int[] {curr[0] + k, curr[1], curr[2], curr[3] + 1};
            case 4:
                // 위쪽
                return new int[] {curr[0] - k, curr[1], curr[2], curr[3] + 1};
        }

        // 위쪽
        return new int[] {curr[0] - k, curr[1], curr[2], curr[3] + 1};
    }

    // Turn
    private static int[] getNextTurn(int[] curr, int dir) {
        if (dir == 0) {
            // 왼쪽으로 90도 회전
            switch (curr[2]) {
                case 1:
                    // 오른쪽 -> 위쪽
                    return new int[] {curr[0], curr[1], 4, curr[3] + 1};
                case 2:
                    // 왼쪽 -> 아래쪽
                    return new int[] {curr[0], curr[1], 3, curr[3] + 1};
                case 3:
                    // 아래쪽 -> 오른쪽
                    return new int[] {curr[0], curr[1], 1, curr[3] + 1};
                case 4:
                    // 위쪽 -> 왼쪽
                    return new int[] {curr[0], curr[1], 2, curr[3] + 1};
            }

            return new int[] {curr[0], curr[1], 2, curr[3] + 1};
        } else {
            // 오른쪽으로 90도 회전
            switch (curr[2]) {
                case 1:
                    // 오른쪽 -> 아래쪽
                    return new int[] {curr[0], curr[1], 3, curr[3] + 1};
                case 2:
                    // 왼쪽 -> 위쪽
                    return new int[] {curr[0], curr[1], 4, curr[3] + 1};
                case 3:
                    // 아래쪽 -> 왼쪽
                    return new int[] {curr[0], curr[1], 2, curr[3] + 1};
                case 4:
                    // 위쪽 -> 오른쪽
                    return new int[] {curr[0], curr[1], 1, curr[3] + 1};
            }

            return new int[] {curr[0], curr[1], 1, curr[3] + 1};
        }
    }

    private static boolean canMove(int[] next) {
        if (next[0] <= 0 || next[0] > m || next[1] <= 0 || next[1] > n) {
            return false;
        }

        if (board[next[0]][next[1]] == 1) return false;

        return true;
    }
}

[yu-heejin]

추가로 고려할 점: 가다가 장애물이 등장하면 안됨 현재 문제점은 단순히 직진만 하고 가는 길의 장애물을 고려하지 않음