[Algorithm]Baekjoon 8972번 :: 미친 아두이노

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

8972번: 미친 아두이노

 

 

struct Node
{
    int y;
    int x;
};
 
int r, c;
char arr[101][101];
int visited[101][101] = { 0 };
queue<int> dirInfo;
int playerY;
int playerX;
int dir[10][2] = { {-3333,-3333}, {1,-1}, {1,0}, {1,1}, {0,-1}, {0,0}, {0,1}, {-1,-1}, {-1,0}, {-1,1} }; 
 
vector<Node> curLivedRobots;
queue<Node> crazyLobotsArr[101][101];
 
bool playerMove() // 무사히 이동했을 경우 true 리턴.
{
    int nextDir = dirInfo.front();
    dirInfo.pop();
 
    arr[playerY][playerX] = '.'; // 현재위치 빈공간으로 일단 만들어두기. 이동할거니까
 
    playerY += dir[nextDir][0];
    playerX += dir[nextDir][1];
    // 좌표만 업뎃. 아직 arr에 반영안함.
 
    if (arr[playerY][playerX] == 'R') // 로봇만나면
    {
        return false;
    }
    else // 빈칸이면
    {
        arr[playerY][playerX] = 'I';
    }
 
    return true;
}
 
bool crazyRobotMove() // 로봇 이동을 '전부' 다 끝낸 후, 같은칸 검사해서 2개이상이면 다 폭발시키기.
{                      // 플레이어 만나서 겜 종료시 false 리턴
    vector<Node> movedCrazyLobots;
 
    for (int i = 0; i < curLivedRobots.size(); ++i)
    {
        int curY = curLivedRobots[i].y;
        int curX = curLivedRobots[i].x;
 
        int minIndex = 1000;
        int minDistance = 10000000;
 
        for (int j = 1; j <= 9; ++j)
        {
            int nextY = curY + dir[j][0];
            int nextX = curX + dir[j][1];
 
            int distance = abs(nextY - playerY) + abs(nextX - playerX);
            if (distance < minDistance)
            {
                minDistance = distance;
                minIndex = j;
            }
        }
 
        if (crazyLobotsArr[curY][curX].size() == 1) // 현재 자기자신만 있을때 .으로 표시
        {
            arr[curY][curX] = '.';
        }
        
        crazyLobotsArr[curY][curX].pop();
        
        int nextY = curY + dir[minIndex][0];
        int nextX = curX + dir[minIndex][1];
 
        if (arr[nextY][nextX] == 'I') return false; // 플레이어있으면 게임 끝.
 
        crazyLobotsArr[nextY][nextX].push({ nextY,nextX });
        movedCrazyLobots.push_back({ nextY,nextX });
 
        arr[nextY][nextX] = 'R'; 
    }
 
    for (int i = 0; i < movedCrazyLobots.size(); ++i)
    {
        int curY = movedCrazyLobots[i].y;
        int curX = movedCrazyLobots[i].x;
        queue<Node>& curQueue = crazyLobotsArr[curY][curX];
 
        if (curQueue.size() >= 2) // 2개이상 모여잇으면
        {
            arr[curY][curX] = '.';
            while (!curQueue.empty()) // 터뜨리기
            {
                curQueue.pop();
            }
        }
    }
 
    curLivedRobots.clear();
 
    for (int i = 0; i < movedCrazyLobots.size(); ++i)
    {
        int curY = movedCrazyLobots[i].y;
        int curX = movedCrazyLobots[i].x;
        queue<Node>& curQueue = crazyLobotsArr[curY][curX];
 
        if (curQueue.size() == 1) // 1개짜리들만
        {
            curLivedRobots.push_back({ curY,curX });
        }
    }
 
    return true;
}
 
void print()
{
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            printf("%c", arr[i][j]);
        }
        printf("\n");
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'I')
            {
                playerY = i;
                playerX = j;
            }
            else if (arr[i][j] == 'R')
            {
                crazyLobotsArr[i][j].push({ i,j });
                curLivedRobots.push_back({ i,j });
                visited[i][j] = 1;
            }
        }
    }
 
    string temp;
 
    cin >> temp;
 
    for (int i = 0; i < temp.size(); ++i)
    {
        dirInfo.push(temp[i] - '0');
    }
 
    int dirSize = dirInfo.size();
    
    while (1)
    {
        if (!playerMove())
        {
            cout << "kraj " << dirSize - dirInfo.size();
            return 0;
        }
        if (!crazyRobotMove())
        {
            cout << "kraj " << dirSize - dirInfo.size();
            return 0;
        }
 
        if (dirInfo.empty())
        {
            break;
        }
    }
 
    print();
 
    return 0;
}

 

여타 문제처럼 꼼꼼하게 구현하면 많이 어렵지는 않다.

조금이라도 뭔가를 놓치면 디버깅하기가 상당히 귀찮고 오래걸리니 사실 선호하는 문제유형은 아니긴 하다..

 

주의해야할 것은 미친아두이노로봇은 이동을 모두 마친 후에, 이동자리를 검사해서 2개이상일 때 터트려야한다는 것이다.

하나하나 이동시키는 도중에 2개가 됐다고 터트리면 안된다.

이 부분을 뭔가 굉장히 효율적으로 처리하지는 못하고 거의 반하드코딩식?으로 한 것 같다.

나같은 경우는 그냥 아예 queue<Node> crazyLobotsArr을 따로 사용해서 풀었다.

이동을 모두 마친 후, 해당좌표의 큐 크기가 2이상일 경우 터트리는 식으로 했다.