[백준]#2174 로봇 시뮬레이션

문제

가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다. 이 땅 위에 로봇들이 N(1≤N≤100)개 있다.

로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. 위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다. 또한 각 로봇은 맨 처음에 NWES 중 하나의 방향을 향해 서 있다. 초기에 서 있는 로봇들의 위치는 서로 다르다.

이러한 로봇들에 M(1≤M≤100)개의 명령을 내리려고 한다. 각각의 명령은 순차적으로 실행된다. 즉, 하나의 명령을 한 로봇에서 내렸으면, 그 명령이 완수될 때까지 그 로봇과 다른 모든 로봇에게 다른 명령을 내릴 수 없다. 각각의 로봇에 대해 수행하는 명령은 다음의 세 가지가 있다.

1. L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다.
2. R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다.
3. F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다.

간혹 로봇들에게 내리는 명령이 잘못될 수도 있기 때문에, 당신은 로봇들에게 명령을 내리기 전에 한 번 시뮬레이션을 해 보면서 안전성을 검증하려 한다. 이를 도와주는 프로그램을 작성하시오.

잘못된 명령에는 다음의 두 가지가 있을 수 있다.

1. Robot X crashes into the wall: X번 로봇이 벽에 충돌하는 경우이다. 즉, 주어진 땅의 밖으로 벗어나는 경우가 된다.
2. Robot X crashes into robot Y: X번 로봇이 움직이다가 Y번 로봇에 충돌하는 경우이다.

입력

첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순서대로 주어진다. 각각의 명령은 명령을 내리는 로봇, 명령의 종류(위에 나와 있는), 명령의 반복 회수로 나타낸다. 각 명령의 반복 회수는 1이상 100이하이다.

출력

첫째 줄에 시뮬레이션 결과를 출력한다. 문제가 없는 경우에는 OK를, 그 외의 경우에는 위의 형식대로 출력을 한다. 만약 충돌이 여러 번 발생하는 경우에는 가장 먼저 발생하는 충돌을 출력하면 된다.

예제 입력 1

5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7

예제 출력 1

Robot 1 crashes into the wall

풀이

이 문제는 특별한 알고리즘을 사용하기 보다는 문제에 주어진 조건을 착실히 구현해내면 풀 수 있는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map;
    static int row;
    static int col;
    static Pair[] robots;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        row = Integer.parseInt(input[1]);
        col = Integer.parseInt(input[0]);
        input = br.readLine().split(" ");
        map = new int[row+1][col+1];

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        robots = new Pair[N+1];

        for(int i=1; i<=N; i++) {
            input = br.readLine().split(" ");
            int d = 0;

            if(input[2].equals("W"))
                d = 1;

            else if(input[2].equals("E"))
                d = 3;

            else if(input[2].equals("S"))
                d = 2;

            robots[i] = new Pair(row-Integer.parseInt(input[1])+1, Integer.parseInt(input[0]), d);
            map[robots[i].x][robots[i].y] = i;
        }

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            int ans = sol(Integer.parseInt(input[0]), input[1], Integer.parseInt(input[2]));
            if(ans<0)
                return;
        }
        System.out.println("OK");
    }

    public static int sol(int num, String str, int time) {
        Pair robot = robots[num];
        map[robot.x][robot.y] = 0;
        int nd = robot.d;
        int nx = robot.x;
        int ny = robot.y;

        for(int i=0; i<time; i++) {
            if(str.equals("L")) {
                if(nd==3)
                    nd=0;
                else
                    nd+=1;
            }

            else if(str.equals("R")) {
                if(nd==0)
                    nd=3;
                else
                    nd-=1;
            }

            else {
                nx += dx[nd];
                ny += dy[nd];

                if(nx<1 || nx>row || ny<1 || ny>col) {
                    System.out.println("Robot "+num+" crashes into the wall");
                    return -1;
                }

                if(map[nx][ny]!=0) {
                    System.out.println("Robot "+num+" crashes into robot "+map[nx][ny]);
                    return -1;
                }
            }
        }
        map[nx][ny] = num;
        robots[num] = new Pair(nx, ny, nd);

        return 1;
    }

    public static class Pair {
        int x;
        int y;
        int d;

        public Pair(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}