[SIM] 2174번 로봇 시뮬레이션

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번 로봇에 충돌하는 경우이다.

 

입력

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

 

출력

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

 

예제 입력

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

5 4
2 4
1 1 E
5 4 W
1 F 3
2 F 1
1 L 1
1 F 3

5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2

5 4
2 3
1 1 E
5 4 W
1 F 4
1 L 1
1 F 20

 

예제 출력

Robot 1 crashes into the wall

Robot 1 crashes into robot 2

OK

Robot 1 crashes into robot 2

 

해결방법

주어진 명령을 구현하는 간단한 시뮬레이션 문제이다

 

 

⭐️ 솔루션 ⭐️

• 처음에 로봇을 입력할 때, 우리가 사용하는 벡터와 인덱스가 다르기 때문에 좌표 처리를 해준다
• 모든 로봇은 벡터로 관리한다
• 만약 i 번째 로봇에 대해 명령을 한다면 벡터의 i 번째에서 로봇의 정보를 빼내와 명령을 수행한 뒤 수정된 로봇의 정보를 다시 넣어준다

 

 

전체적인 문제 흐름은 다음과 같다

1. 명령을 수행할 로봇의 인덱스를 사용해 벡터에서 로봇의 정보를 빼온다
2. 반복 횟수만큼 반복문을 수행한다
3. 만약 회전하는 명령이라면 종료 조건에 위배되는게 없으므로 수행한다
4. 만약 전진하는 명령이라면 앞으로 한칸 전진 후, 이동한 노드가 벽이 아니거나 다른 로봇과 부딪치지 않는다면 좌표를 수정한다
5. 반복횟수 만큼 무사히 명령을 수행했다면 벡터에서 로봇의 좌표를 수정해준다

 

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 1988 KB

시간 : 0 ms

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;

struct robot {
    int x,y,dir;
    
    robot() { }
    robot(int _x,int _y,int _dir) : x(_x),y(_y),dir(_dir) { }
};

int n,m;
int robotCnt,robotX,robotY;
int orderCnt,orderInd,orderRepeat;
char robotDir,orderKind;
bool flag;

int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,1,-1,0,0};

vector<robot> allRobot;

// 방향 전환
int changeDir(int dir,char c){
    if(c == 'L'){
        if(dir == 1) return 4;
        else if(dir == 4) return 2;
        else if(dir == 2) return 3;
        else return 1;
    }
    else{
        if(dir == 1) return 3;
        else if(dir == 3) return 2;
        else if(dir == 2) return 4;
        else return 1;
    }
}

int convertDir(char c){
    if(c == 'E') return 1;
    else if(c == 'W') return 2;
    else if(c == 'S') return 3;
    else return 4;
}

void go(){
    robot tmp = allRobot[orderInd-1];
    int x = tmp.x;
    int y = tmp.y;
    int dir = tmp.dir;
    
    for(int r=0; r<orderRepeat; r++){
        // 명령 : 앞으로 한 칸 전진
        if(orderKind == 'F'){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            // 벽에 부딪치는 경우
            if(nx<=0 || ny<=0 || nx>n || ny>m){
                cout << "Robot " << orderInd <<" crashes into the wall" << "\n";
                flag = false;
                return;
            }
            
            // 다른 로봇과 부딪치는 경우
            for(int i=0; i<allRobot.size(); i++){
                if(i == orderInd-1) continue;
                
                if(allRobot[i].x == nx && allRobot[i].y == ny){
                    cout << "Robot " << orderInd << " crashes into robot " << i+1 << "\n";
                    flag = false;
                    return;
                }
            }
            
            // 무사히 앞으로 한 칸 전진했다면 좌표 수정
            x = nx;
            y = ny;
        }
        // 명령 : 방향 전환
        else{
            dir = changeDir(dir, orderKind);
        }
    }
    
    // 로봇이 반복횟수만큼 무사히 명령을 수행했다면 로봇 좌표 및 방향 수정
    if(flag){
        allRobot[orderInd-1].x = x;
        allRobot[orderInd-1].y = y;
        allRobot[orderInd-1].dir = dir;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> m >> n;
    
    cin >> robotCnt >> orderCnt;
    for(int i=0; i<robotCnt; i++){
        cin >> robotY >> robotX >> robotDir;
        
        int nx = n - robotX + 1;
        int nd = convertDir(robotDir);
        
        allRobot.push_back(robot(nx,robotY,nd));
    }
    
    for(int i=0; i<orderCnt; i++){
        cin >> orderInd >> orderKind >> orderRepeat;
        
        // 로봇 명령 수행
        flag = true;
        go();
        
        if(!flag) exit(0);
    }
    
    cout << "OK" << "\n";
    
    return 0;
}