BOJ 1726 로봇

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

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

---

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

---

예제 입력 1

5 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 0 0 0 0
0 0 1 1 1 0
1 0 0 0 0 0
4 2 3
2 4 1

예제 출력 1

9

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Position {
        int row, col, dir;

        public Position(int row, int col, int dir) {
            this.row = row;
            this.col = col;
            this.dir = dir;
        }

        public boolean equals(Position position) {
            return row == position.row && col == position.col && dir == position.dir;
        }
    }

    static int M, N;
    static int[][] map;

    // 각 방향마다 방문한 지역을 체크하기 위한 3차원 배열
    static boolean[][][] visited;

    static int[] dirRow = {-1, 0, 1, 0}, dirCol = {0, 1, 0, -1};

    // 가능한 명령의 목록이다.
    // 각 배열의 첫 번째 변수는 움직일 거리를 의미, 두 번째 변수는 방향을 의미 / ex) commands[0][0] => 앞으로 0칸 전진, 왼쪽으로 회전
    // 0번째 명령은 왼쪽으로 회전, 1번째 명령은 오른쪽으로 회전, 2번째 부터 마지막 명령까지 각각 1 ~ 3칸 전진을 의미한다.
    static int[][] commands = { {0, -1}, {0, 1}, {1, 0}, {2, 0}, {3, 0} };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        // 공장의 map 초기화
        map = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 동서남북 각 방향마다 특정 공간의 방문 여부 체크를 위한 배열 초기화
        visited = new boolean[M][N][4];
        Queue<Position> queue = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        // 시작점 입력
        Position start = new Position(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()));
        initDir(start); // 이 코드에 맞게 방향 재설정
        visited[start.row][start.col][start.dir] = true; // 시작점 방문 처리
        queue.offer(start);

        st = new StringTokenizer(br.readLine());
        // 도착점 입력
        Position goal = new Position(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()));
        initDir(goal); // 이 코드에 맞게 방향 재설정

        int level = 0;
        // 시작점이 도착점일 경우, 0 출력 후 종료
        if(start.equals(goal)) {
            System.out.println(level);
            return;
        }

        while (!queue.isEmpty()) {
            level++;
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                Position check = queue.poll();

                for (int[] command: commands) {
                    // 명령에 따라 수정될 방향 계산
                    int newDir = (4 + check.dir + command[1]) % 4;

                    // 명령에 따라 이동할 위치 계산
                    Position newPos = new Position(check.row + dirRow[newDir] * command[0], check.col + dirCol[newDir] * command[0], newDir);

                    boolean isInside = newPos.row >= 0 && newPos.row < M && newPos.col >= 0 && newPos.col < N;

                    // 이동할 곳이 map 안에 있고, 궤도가 깔려있지 않고, 방문하지 않은 곳일 경우
                    if(isInside && map[newPos.row][newPos.col] == 0 && !visited[newPos.row][newPos.col][newPos.dir]) {
                        // 도착점에 도착했을 때, 지금까지 진행한 명령의 수를 출력 후 종료
                        if(newPos.equals(goal)) {
                            System.out.println(level);
                            return;
                        }
                        
                        // 도착점이 아닐 경우, 이동할 Position을 방문처리 후, queue에 offer
                        visited[newPos.row][newPos.col][newPos.dir] = true;
                        queue.offer(newPos);
                    }
                    // 이동할 곳이 map 안에 있지만, 궤도가 깔린 곳이고, 전진 명령일 경우 더 이상의 명령 검사를 종료한다.
                    // 왜냐하면, 명령 검사 순서가 왼쪽, 오른쪽 회전 이후에 1 ~ 3칸 전진 명령 순으로 이루어지는데,
                    // 앞에 궤도가 있다면 이후에 전진은 불가능하기 때문에 순간이동이 가능하지 않은 한, 더 이상의 명령 검사를 하면 안된다.
                    else if (isInside && map[newPos.row][newPos.col] == 1 && command[0] > 0) break;
                }
            }
        }
    }

    // 문제에서는 동서남북을 각각 1,2,3,4로 표현했지만, 이 코드에서는 동서남북을 1,3,2,0으로 표현했다.
    // 따라서 입력받은 방향을 이 코드에 맞게 수정하기 위한 메소드이다.
    static void initDir(Position pos) {
        switch (pos.dir) {
            case 2: pos.dir = 3; break;
            case 3: pos.dir = 2; break;
            case 4: pos.dir = 0; break;
        }
    }
}