[2174] 로봇 시뮬레이션

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

2174번: 로봇 시뮬레이션

<문제>

2차원 배열에서 로봇이 상하좌우로 움직이고, 과정중 충돌(로봇<->벽 || 로봇<->로봇)이 발생하는지를 판별해야한다.

어떠한 알고리즘도 요구하지 않지만, X와 Y가 2차원배열과는 달라 이 부분을 주의해야한다.

애초에 배열을 좌표평면처럼 쓰거나, 아예 변환해버린 뒤 사용하는 등의 작업이 필요한데

아래의 코드는 문제의 x와 y를 (R,C)로 변환해준 코드다. 

 

대체로 이런문제(순수한 구현/시뮬레이션)같은 경우 비슷비슷한 의미의 변수를 사용할 상황도 많이 나오고,

그렇기에 변수의 이름을 한글자짜리로 짓는게 아니라 이름만으로도 알아볼 수 있게 작성하거나

주석을 세세히 달아주며 코딩하는것이 훨씬 디버깅에 편리하다.

 

최선의 방법은 아니지만, 나만의 규칙을 만들어두는것도 좋다. 예를들어 (R,C)를 항상 (y,x)로 쓴다거나.

4방향을 나타내는 0~3의 값을 갖는 변수명은 key로 한다거나. bfs에서 현재정점에 대한 정보는 cur로 받는다거나...

물론 실무에서, 혹은 협업할때 사용할법한 방법은 아니지만 말이다.

 

 

우선, 우리가 필요한건 '어느' 위치에 로봇이 존재하는가이다. 로봇은 하나가 움직일동안 다른것은 고정되어 있고,

경로역시 input으로 주어진다. 그렇기에 해당 로봇이 이동할 경로중 하나라도 벽, 로봇이 있다면 바로 연산을 종료한다.
(연산을 종료한다는 말은 시뮬레이션을 중단한다는 뜻이다)

우리가 궁금한건 충돌이 '어떻게' 발생하는가이지, 몇개 발생하는것이 아니기 때문이다. 그렇기에 map을 bool로 선언해줄 수 있겠다. 

다만, 로봇과 로봇간의 충돌에는 '몇번'로봇이 '몇번'로봇에게 충돌했는지를 출력해야 하므로, 맵에 로봇의 번호도 같이 저장하기 위해 bool이 아닌 int로 선언, 로봇이 존재할경우 로봇의 번호를 저장하고 로봇이 없다면 0을 저장해줬다.

벽으로의 충돌은 로봇과의 충돌에 비해 매우 간단하게 구현할 수 있다. 이는 로봇이 맵의 테두리에 고정적으로 위치해서, 전혀 움직이지 않는 것으로도 생각할 수 있다. 움직이지 않는 로봇은, 업데이트가 필요없다.

마지막으로 충돌이 발생하지 않는 input에 대해서는 조기종료 없이 모든 시뮬레이션을 수행하고, 시뮬레이션이 끝났음에도 조기종료가 발생하지 않았다면 그냥 OK를 출력하면 되는것이다.

 

 

이제 로봇을 실제로 움직이는 부분을 다뤄보자.

우리는 로봇의 시작위치와 로봇의 이동 방향과 횟수까지 전부 알고있다.(input으로 들어온다)

그렇지만, 이를 단순히 아래처럼 상수시간으로 다음 위치를 계산하면 안된다.
curY = curY+(dy[i] * rep), curX = curX + (dx[i] * rep) // rep : 반복횟수

이는 당연히 경로진행 도중 로봇이 존재하는지에 대한 판별이 불가능하기 때문이다.

그렇기에 O(1)로 처리할수도 있는것을, O(rep)동안 처리해주어야 하고, 그 도중 충돌이 발생하면 조기종료 하면 된다.

조기종료가 없었다면 어떻게 업데이트하면 될까?

이전위치를 {startY, startX}, 이후 위치를 {curY, curX}, 로봇의 번호를 num, 맵을 check라고 할때

check[startY][startX]=0
check[curY][curX]=num

위 두문장으로 업데이트가 이루어진다.

 

이동에 대한 처리는 끝났다. 남은 방향회전에 대한 처리는 key(로봇의 방향을 나타내는 0~3의 int형 변수)를

1씩 증가시키냐, 감소시키냐정도이다. 이부분은 이동에 비해 간단하게 처리된다.

 

 

마지막으로, 2차원 배열에 현재 로봇의 위치는 check[][]로 저장했지만, 방향 역시 같이 저장해줄 필요가 있다.

이는,  vector {Y, X, key}의 형태로 로봇의 번호로 구분해서 저장해주었다.

가령, v[5]에는 5번로봇의 행, 열, 방향이 저장된 셈이다.

 

<소스코드>

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n, m, robotNum, cmdNum;
vector <pair<int, pair<int, int>>>v;
int check[101][101];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int main(void) {
    cin.tie(0);
    int i, j;
    scanf("%d %d", &m, &n);
    scanf("%d %d", &robotNum, &cmdNum);
    v.resize(103);
    for (i = 1; i <= robotNum; i++) {
        int x = 0, y = 0;
        char dir = 0;
        cin >> x >> y >> dir;
        y = n - y + 1;
        check[y][x] = i;//로봇의 번호를 저장
        if (dir == 'E')v[i] = { y,{x,0} };
        else if (dir == 'S')v[i] = { y,{x,1} };
        else if (dir == 'W')v[i] = { y,{x,2} };
        else if (dir == 'N')v[i] = { y,{x,3} };
    }
    for (i = 1; i <= cmdNum; i++) {
        int num = 1, rep = 0;
        char op = 0;
        cin >> num >> op >> rep;
        int startY = v[num].first;
        int startX = v[num].second.first;
        int key = v[num].second.second;//우하좌상, 0123
        int newKey = key;
        int cnt = 0;
        if (op == 'F') {
            int curX = startX, curY = startY;
            while (cnt < rep) {
                curX += dx[key];
                curY += dy[key];
                if (curY > n || curX > m || curX <= 0 || curY <= 0) {//벽과 충돌
                    printf("Robot %d crashes into the wall", num);
                    goto AllBreak;
                }
                if (check[curY][curX] != 0) {//로봇과 충돌
                    printf("Robot %d crashes into robot %d", num, check[curY][curX]);
                    goto AllBreak;
                }
                cnt++;
            }
            check[startY][startX] = 0;
            check[curY][curX] = num;
            v[num] = { curY,{curX,key} };
            continue;
        }
        else if (op == 'L') {
            rep %= 4;
            for (int T = 0; T < rep; T++) {
                newKey--;
                if (newKey == -1)newKey = 3;
            }
            v[num] = { startY,{startX,newKey} };
            continue;
        }
        else if (op == 'R') {
            rep %= 4;
            for (int T = 0; T < rep; T++) {
                newKey = (newKey+1) % 4;
            }
            v[num] = { startY,{startX,newKey} };
            continue;
        }
    }
    printf("OK\n");
AllBreak:
    return 0;
}