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

1. 문제 이해

2차원 배열 위에 로봇들의 위치가 입력으로 주어지고, 해당 로봇들에게 명령을 내리는 문제이다. 명령의 종류는 3가지 이며, 중간에 잘못된 명령이 들어 갈 수 있다. 잘못된 명령일 경우 

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

을 출력하고, 잘못된 명령이 없으면 "OK" 를 출력한다.

---

2. 문제 풀이

2차원 배열의 크기가 가로, 세로 각각 100 이하이며, 로봇들의 수는 100개 이하이다. 명령의 수도 100개 이하이고 각 명령의 반복회수는 100이하이므로 시간 초과를 고려하지 않아도 풀 수있다. 특별한 알고리즘이 필요없는 구현문제임을 알 수 있다.

프로그래밍에서 2차원 배열은 위 그림을 상하반전한 것 처럼 나타낸다. 동작 원리는 똑같으므로 방향에 따른 이동만 잘 구현하면 되고, 좌표만 (0,0) 을 시작으로 바꾸면 된다. ( 안 바꿔도 풀이는 가능하다,)

 

로봇을 2차원 배열에 나타내는데, 로봇의 번호만 배열에 나타낸다. 그리고 로봇의 번호를 인덱스로 하는 1차원 배열을 만들어 로봇의 상태를 저장한다. 간단한 구조체/클래스 를 구현해서 나타낼 수 있다.

 

struct Robot {
    char dir;
    int y;
    int x;
};
vector<Robot> robot(111);
int board[111][111];

2차원 배열 board 에는 로봇의 번호를 적고, 1차원 배열 robot에는 로봇의 상태를 저장한다.

 

입력과 동시에 board와 robot 배열에 각 로봇의 상태를 저장하고, 명령을 입력받는다.

 

1. L

명령이 L 인 경우이다. 이 경우 회전만 하면 되므로 1차원 배열 robot에서 로봇의 상태를 가져와 회전시킨다. 이 때, 4번 회전하면 그대로 이므로 회전 횟수는 4로 나눈 나머지와 똑같다. +1, -1 했을 때의 방향 배열만 잘 만들어 두면 쉽게 구현이 가능하다.

 

2. R 

위 경우와 똑같이 구현한다.

 

3. F

 로봇이 자신의 방향대로 이동하는 경우이다. 벽에 부딪히더라도 중간에 로봇을 만나서 부딪히면 Output이 달라지기 때문에 한 칸씩 이동시키거나, 로봇의 이동할 방향에 로봇이나 벽에 있는지 없는지 체크해야 한다. 두 가지 방법 비슷하기 때문에 한 칸씩 이동시키는 것을 선택했다.

 로봇이 자신의 방향대로 한 칸 이동가능하면, 2차원 배열의 정보와 1차원 배열의 로봇 정보를 바꿔준다. 만약 중간에 벽에 부딪히거나 로봇에 부딪히면 바로 프로그램을 종료시킨다.

---

3. 제출 결과

---

4. 문제 코드

#include <bits/stdc++.h>
using namespace std;
int board[111][111];
char dir_type[4] = {'N', 'W', 'S', 'E'};
int dir_move[4][2] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
unordered_map<char, int> um;
void dirInit() {
    for(int i=0; i<4; i++) {
        um.insert({dir_type[i], i});
    }
}
struct Robot {
    char dir;
    int y;
    int x;
};
vector<Robot> robot(111);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    dirInit();

    int A,B; cin >> A >> B;
    int N,M; cin >> N >> M;
    for(int i=1; i<=N; i++) {
        int x,y; cin >> x >> y;
        char dir; cin >> dir;
        board[y-1][x-1] = i;
        robot[i] = {dir, y-1, x-1};
    }

    int r, cnt; char t;
    while(M--) {
        cin >> r >> t >> cnt;
        if ( t == 'L') {
            cnt %= 4;
            int robot_dir = um.find(robot[r].dir)->second;
            while(cnt > 0) {
                robot_dir++;
                if(robot_dir > 3 ) { robot_dir = 0;}
                cnt--;
            }
            robot[r].dir = dir_type[robot_dir];
        } else if ( t == 'R' ) {
            cnt %= 4;
            int robot_dir = um.find(robot[r].dir)->second;
            while(cnt > 0) {
                robot_dir--;
                if(robot_dir < 0) { robot_dir = 3;}
                cnt--;
            }
            robot[r].dir = dir_type[robot_dir];
        } else if ( t == 'F') {
            int robot_dir = um.find(robot[r].dir)->second;
            while(cnt > 0) {
                int dy = robot[r].y + dir_move[robot_dir][0];
                int dx = robot[r].x + dir_move[robot_dir][1];
                
                if(dy <0 || dx <0 || dy >= B || dx >= A) {
                    printf("Robot %d crashes into the wall", r);
                    exit(0);
                }
                if(board[dy][dx] != 0) {
                    printf("Robot %d crashes into robot %d", r, board[dy][dx]);
                    exit(0);
                } else {
                    board[robot[r].y][robot[r].x] = 0;
                    board[dy][dx] = r;
                    robot[r].y = dy;
                    robot[r].x = dx;
                }
                cnt --;
            }
        }
    }
    cout << "OK";
}