[BaekJoon] 1726 로봇 (Java)

1.  문제 링크

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

2.  문제

요약

• 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나입니다.
• 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지입니다.
  • 명령 1. Go k : k는 1, 2 또는 3일 수 있습니다. 현재 향하고 있는 방향으로 k칸만큼 움직입니다.
  • 명령 2. Turn dir : dir은 left 또는 right이며, 각각 왼쪽 또는 오른쪽으로 90° 회전합니다.
• 공장 내 궤도가 설치되어 있는 상태가 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력되는데, 0은 궤도가 깔려있어 로봇이 갈 수 있는 지점이고 1은 궤도가 없어 로봇이 갈 수 없는 지점을 의미합니다.
• 로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 문제입니다.
• 입력: 첫 번째 줄에 100보다 작거나 같은 자연수인 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 주어지고 두 번째 줄부터 M개의 줄에 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어집니다. 그 다음 줄에는 로봇의 출발 지점의 위치(행과 열의 번호)와 바라보는 방향이 주어집니다. 마지막 줄에는 로봇의 도착 지점의 위치(행과 열의 번호)와 바라보는 방향이 주어집니다.
  • 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어집니다.
  • 출발지점에서 도착지점까지는 항상 이동이 가능합니다.
• 출력: 첫 번째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static Robot start, end;
    static void input() {
        Reader scanner = new Reader();
        M = scanner.nextInt();
        N = scanner.nextInt();
        map = new int[M][N];
        for(int row = 0; row < M; row++) {
            for(int col = 0; col < N; col++)
                map[row][col] = scanner.nextInt();
        }
        start = new Robot(scanner.nextInt() - 1, scanner.nextInt() - 1, 0, scanner.nextInt());
        end = new Robot(scanner.nextInt() - 1, scanner.nextInt() - 1, 0, scanner.nextInt());
    }

    static void solution() {
        System.out.println(bfs(start, end));
    }

    static int bfs(Robot start, Robot end) {
        int[][] turnDir = {{0, 0}, {3, 4}, {3, 4}, {1, 2}, {1, 2}};
        int[] dx = {0, 0, 0, 1, -1}, dy = {0, 1, -1, 0, 0};
        PriorityQueue<Robot> queue = new PriorityQueue<>();
        int[][][] visited = new int[M][N][5];
        for(int row = 0; row < M; row++) {
            for(int col = 0; col < N; col++)
                Arrays.fill(visited[row][col], Integer.MAX_VALUE);
        }
        visited[start.x][start.y][start.direction] = 0;
        queue.offer(new Robot(start.x, start.y, 0, start.direction));
        int answer = 0;
        while(!queue.isEmpty()) {
            Robot cur = queue.poll();
            if(cur.x == end.x && cur.y == end.y && cur.direction == end.direction) {
                answer = cur.moveNum;
                break;
            }
            for(int move = 1; move <= 3; move++) {
                int cx = cur.x + dx[cur.direction] * move, cy = cur.y + dy[cur.direction] * move;
                if(isInMap(cx, cy)) {
                    if(map[cx][cy] == 1) break;
                    if(visited[cx][cy][cur.direction] > visited[cur.x][cur.y][cur.direction] + 1) {
                        visited[cx][cy][cur.direction] = visited[cur.x][cur.y][cur.direction] + 1;
                        queue.offer(new Robot(cx, cy, visited[cx][cy][cur.direction], cur.direction));
                    }
                }
            }
            for(int dir = 0; dir < turnDir[cur.direction].length; dir++) {
                int direction = turnDir[cur.direction][dir];
                if(visited[cur.x][cur.y][direction] > visited[cur.x][cur.y][cur.direction] + 1) {
                    visited[cur.x][cur.y][direction] = visited[cur.x][cur.y][cur.direction] + 1;
                    queue.offer(new Robot(cur.x, cur.y, visited[cur.x][cur.y][direction], direction));
                }
            }
        }
        return answer;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < M && y >= 0 && y < N) return true;
        return false;
    }

    static class Robot implements Comparable<Robot> {
        int x, y, moveNum, direction;
        public Robot(int x, int y, int moveNum, int direction) {
            this.x = x;
            this.y = y;
            this.moveNum = moveNum;
            this.direction = direction;
        }

        @Override
        public int compareTo(Robot r) {
            return this.moveNum - r.moveNum;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• BFS 탐색 시에 명령 횟수 및 방향을 나타내기 위해 Robot 클래스를 생성합니다.
  • 이 클래스는 현재 지점의 x y 좌표, 지금까지의 명령 수행 횟수 moveNum, 현재 바라보고 있는 방향 direction을 멤버로 가집니다.
  • direction은 1일 때는 동쪽, 2일 때는 서쪽, 3일 때는 남쪽, 4일 때는 북쪽을 나타냅니다.
  • 이후에 BFS 탐색에서 PriorityQueue를 이용할 것이기 때문에 Comparator 인터페이스를 구현하여 명령 수행 횟수가 적은 순으로 정렬되도록 합니다.
• BFS 탐색을 통해 출발지점에서 도착지점의 원하는 방향으로 이동하는 최소 명령 횟수를 구합니다.
  • turnDir이라는 2차원 배열을 생성하고 각 방향에서 회전할 수 있는 방향들을 저장합니다.
  • dx, dy 1차원 배열을 생성하여 각 방향에서 가로로 이동하는 양, 세로로 이동하는 양읗 넣어줍니다.
  • PriorityQueue를 생성하고 출발지점에서의 좌표와 방향을 Robot 객체로 생성하여 PriorityQueue에 넣어줍니다.
  • 각 위치에서 각 방향에 대해 방문 체크를 하기 위해 3차원 배열 visited를 생성하고 출발지점 좌표에서의 출발 방향의 visited 값을 0으로 초기화합니다.
  • PriorityQueue가 비워지기 전까지 PriorityQueue에서 Robot 객체를 하나씩 뽑아 두 명령을 수행해보면서 각 위치를 탐색해 최소 명령 수행 횟수를 구합니다.
    • PriorityQueue에서 Robot 객체를 하나 뽑습니다. 이를 편의상 cur이라고 하겠습니다.
    • 만약 cur의 x, y 좌표, 방향이 도착지점의 x, y 좌표, 방향과 일치하다면 cur의 moveNum이 답이 됩니다.
    • 그렇지 않다면 현재 바라보고 있는 방향으로 1 ~ 3칸 이동해보면서 해당 위치가 공장 내에 존재하고 궤도가 깔려있으며(공장 내 궤도 설치 상태를 나타내는 값이 0) 해당 위치의 현재 방향에서의 visited 값이 (cur의 위치의 현재 방향에서의 visited 값 + 1)보다 크다면 해당 위치의 현재 방향으로 더 적은 명령 수행을 하여 이동할 수 있기 때문에 해당 위치의 현재 방향에서의 visited 값을 (cur의 위치의 현재 방향에서의 visited 값 + 1)로 변경하고 해당 위치의 좌표, 명령 수행 횟수, 방향을 Robot 객체로 만들어 PriorityQueue에 넣어 다음 탐색에 활용합니다.
    • 또한, 현재 위치에서 방향을 오른쪽, 왼쪽으로 회전하여 그 때의 visited값이 (cur의 위치의 현재 방향에서의 visited 값 + 1)보다 크다면 역시 마찬가지로 더 적은 명령 수행을 하여 해당 방향을 바라볼 수 있다는 뜻이므로 그 때의 visited 값을 (cur의 위치의 현재 방향에서의 visited 값 + 1)로 변경하고 현재 위치의 좌표, 명령 수행 횟수, 방향을 Robot 객체로 만들어 PriorityQueue에 넣어 다음 탐색에 활용합니다.