백준 - 2174번(로봇 시뮬레이션)

문제 출처: https://www.acmicpc.net/problem/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번 로봇에 충돌하는 경우이다.

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

public class Main {

    private static int[][] directions = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, }; // N, E, S, W 순서

    private static class Robot {

        int direction;    // 로봇 방향
        int y;            // y 좌표
        int x;            // x 좌표

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

    }

    private static int[][] map;
    private static Robot[] robots;
    private static int A, B;
    private static StringBuilder sb = new StringBuilder("OK");

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        A = Integer.parseInt(tokenizer.nextToken());    // 가로(열)
        B = Integer.parseInt(tokenizer.nextToken());    // 세로(행)

        map = new int[B + 1][A + 1];

        tokenizer = new StringTokenizer(reader.readLine());

        int N = Integer.parseInt(tokenizer.nextToken());    // 로봇의 수
        int M = Integer.parseInt(tokenizer.nextToken());    // 명령의 수

        robots = new Robot[N + 1];

        for (int i = 1; i <= N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokenizer.nextToken());    // x 좌표
            int y = Integer.parseInt(tokenizer.nextToken());    // y 좌표
            String direction = tokenizer.nextToken();           // 방향

            robots[i] = new Robot(findDirection(direction), y, x);

            map[y][x] = i;
        }

//        for (int[] row : map) {
//            System.out.println(Arrays.toString(row));
//        }

//        System.out.println();

        // 명령
        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int num = Integer.parseInt(tokenizer.nextToken());  // 로봇 번호
            String command = tokenizer.nextToken(); // 명령
            int repeat = Integer.parseInt(tokenizer.nextToken());   // 반복 횟수

            for (int j = 0; j < repeat; j++) {
                performCommand(command, num);
            }

//            for (int[] row : map) {
//                System.out.println(Arrays.toString(row));
//            }
//            System.out.println();

            if (sb.length() > 2) {
                // 값의 변화가 생김 -> 끝
                break;
            }
        }

        System.out.println(sb);
    }

    private static void performCommand(String command, int num) {
        Robot current = robots[num];
//        System.out.println("direction: " + current.direction);

        if (command.equals("L")) {
            if (--current.direction < 0) {
                current.direction = 3;
            }
        } else if (command.equals("R")) {
            if (++current.direction > 3) {
                current.direction = 0;
            }
        } else {
            // 전진
            int dy = current.y + directions[current.direction][0];
            int dx = current.x + directions[current.direction][1];

            if (dy >= 1 && dy <= B && dx >= 1 && dx <= A) {
                if (map[dy][dx] != 0) {
                    sb.setLength(0);
                    sb.append("Robot ").append(num).append(" crashes into robot ").append(map[dy][dx]);
                } else {
                    map[dy][dx] = num;
                    map[current.y][current.x] = 0;
                    current.y = dy;
                    current.x = dx;
                }
            } else {
                sb.setLength(0);
                sb.append("Robot ").append(num).append(" crashes into the wall");
            }
        }
    }

    private static int findDirection(String target) {
        switch (target) {
            case "N":
                return 0;

            case "E":
                return 1;

            case "S":
                return 2;

            default:
                return 3;
        }
    }

}

• 구현 문제이다.
• 우선, 배열로 구현하기 위해 북쪽과 남쪽을 x축 대칭 이동시켰다.
• 이에 따라 왼쪽 방향 회전이 오른쪽 회전이 되고, 오른쪽 방향 회전이 왼쪽 회전이 되었다.
• 배열의 순서를 북, 동, 남, 서로 하여 회전할 때마다 인덱스를 더하거나 빼주었다.
• 범위 설정에 주의하자! 배열의 인덱스를 확인할 때 0번 인덱스는 벽으로 처리해야 하나 0까지 들어가게 돼서 96%에서 틀려서 상당히 짜증났었다.