백준 8972 - 미친 아두이노

문제 설명

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.

게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.

1. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
3. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.

---

 

 

 

 

 

 

제한 사항

첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.

마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

보드를 벗어나는 입력은 주어지지 않는다.

---

 

 

 

 

 

 

풀이

주어진 순서대로 시뮬레이션하면 되는 문제이다.

종수의 아두이노는 주어진 방향으로 이동하고, 보드에 놓인 아두이노는 종수의 아두이노와 가까워지도록 이동한다.

 

문제는 그렇게 복잡하지 않다.

8방향의 이동은 y, x의 변화를 배열로 나타내어 계산하면 된다.

vector<int> dy = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };
vector<int> dx = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };

 

종수의 아두이노를 이동시킨 뒤, 보드에 놓여진 아두이노를 이동시켜야 한다.

여기서 한 가지 주의할 점이 있다.

일반적으로는 종수의 아두이노가 있는 칸에 다른 아두이노가 도착하면 게임이 종료된다.

문제에 명시되어 있지 않지만 종수의 아두이노가 다른 아두이노가 있는 칸에 도착해도 게임이 종료된다.

즉, 종수의 아두이노를 이동시키면서 확인을 한 번 더 해야 한다.

 

또, 결과로 보드의 상태를 출력해야 한다.

하지만, 모든 이동에 대해 보드의 상태를 업데이트할 필요는 없다.

모든 이동이 종료된 후, 보드의 이동을 업데이트해도 된다.

 

따라서, 아두이노의 위치를 배열로 관리하여 이동하면 된다.

pair<int, int> Player;
vector<pair<int, int>> Robots;

 

이동하는 것은 간단하다.

변위를 더해주면 된다.

Player.first += dy[dir];
Player.second += dx[dir];

앞서 말했듯이 다른 아두이노의 위치를 확인해야 한다.

for (auto& r : Robots)
{
    if (Player == r)
    {
        cout << "kraj " << t + 1;
        return 0;
    }
}

 

 

다른 아두이노와 같은 위치가 아니라면 종수의 아두이노는 이동을 완료한 것이다.

이제, 다른 아두이노들을 이동시키면 된다.

다른 아두이노들은 이동하여 같은 칸에 도착할 수 있다.

같은 칸에 도착한 아두이노들을 모두 파괴된다.

이는 맵을 통해 간단하게 구현할 수 있다.

bool MoveToPlayer(pair<int, int>& Player, pair<int, int>& Robot)
{
    pair<int, int> result;
    int minDist = INT_MAX;

    for (int i = 0; i < 9; i++)
    {
        if (i == 4) continue;
        int newY = Robot.first + dy[i];
        int newX = Robot.second + dx[i];

        int temp = abs(Player.first - newY) + abs(Player.second - newX);
        if (temp < minDist)
        {
            minDist = temp;
            result = { newY, newX };
        }
    }

    Robot = move(result);
    return minDist == 0;
}

//move robots
map<pair<int, int>, vector<int>> robotPos;
for (int i = 0 ; i < Robots.size(); i++)
{
        if (MoveToPlayer(Player, Robots[i]))
    {
        cout << "kraj " << t + 1;
        return 0;
    }
    robotPos[Robots[i]].push_back(i);
}

아두이노의 위치를 키로 사용하여 만약 value의 값이 2 이상이라면 같은 칸에 도착한 아두이노가 2개 이상이라는 뜻이다.

해당 아두이노들을 제외한 아두이노들만 포함하여 다음 이동을 수행하면 된다.

vector<pair<int, int>> robotTemp;
for (auto itr = robotPos.begin(); itr != robotPos.end(); itr++)
{
    if (itr->second <= 1)
    {
        robotTemp.push_back(itr->first);
    }
}

Robots = move(robotTemp);

새로운 벡터를 이용한 이유는 c++의 벡터는 삭제 연산에 대해 유리하지 않다.

중간의 요소가 삭제되면 이후 요소들을 앞으로 당겨주는 연산이 내부적으로 동작한다.

배열을 기반으로 만들어져 있기 때문이다.

따라서, n개의 요소를 복사하여 만드는 연산이 더욱 짧을 것이라고 판단했다.

또한, move연산을 통해 벡터 자체의 복사 연산을 방지할 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

vector<int> dy = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };
vector<int> dx = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };

bool MoveToPlayer(pair<int, int>& Player, pair<int, int>& Robot)
{
    pair<int, int> result;
    int minDist = INT_MAX;

    for (int i = 0; i < 9; i++)
    {
        if (i == 4) continue;
        int newY = Robot.first + dy[i];
        int newX = Robot.second + dx[i];

        int temp = abs(Player.first - newY) + abs(Player.second - newX);
        if (temp < minDist)
        {
            minDist = temp;
            result = { newY, newX };
        }
    }

    Robot = move(result);
    return minDist == 0;
}

void Print(vector<vector<char>>& Board)
{
    for (auto row : Board)
    {
        for (auto c : row)
        {
            cout << c;
        }
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int R, C;
    cin >> R >> C;

    vector<vector<char>> Board(R, vector<char>(C, '.'));

    pair<int, int> Player;
    vector<pair<int, int>> Robots;
    string Command;

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            char temp;
            cin >> temp;

            if (temp == 'I') Player = { i,j };
            else if (temp == 'R') Robots.push_back({ i,j });
        }
    }

    cin >> Command;

    for (int t = 0; t < Command.size(); t++)
    {
        int dir = (Command[t] - '0') - 1;

        //move player
        Player.first += dy[dir];
        Player.second += dx[dir];

        for (auto& r : Robots)
        {
            if (Player == r)
            {
                cout << "kraj " << t + 1;
                return 0;
            }
        }

        //move robots
        map<pair<int, int>, int> robotPos;
        for (int i = 0 ; i < Robots.size(); i++)
        {
            if (MoveToPlayer(Player, Robots[i]))
            {
                cout << "kraj " << t + 1;
                return 0;
            }
            robotPos[Robots[i]]++;
        }

        vector<pair<int, int>> robotTemp;
        for (auto itr = robotPos.begin(); itr != robotPos.end(); itr++)
        {
            if (itr->second <= 1)
            {
                robotTemp.push_back(itr->first);
            }
        }

        Robots = move(robotTemp);
    }

    Board[Player.first][Player.second] = 'I';
    for (auto& robot : Robots)
    {
        Board[robot.first][robot.second] = 'R';
    }

    Print(Board);

	return 0;
}

---