[백준 8972번] 미친 아두이노 / C++

문제

요즘 종수는 아두이노를 이용해 "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는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

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

출력

중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

풀이

골드4이긴 하지만 문제는 생각보다 쉽게 풀었다!!(조건 처리 제대로 안해서 처음에 틀리긴 했음..)

나는 문제를 쉽게 풀기 위해 종수 아두이노의 위치와 미친 아두이노들의 위치를 모두 저장했다.

그리고 같은 칸에 미친 아두이노가 2개 이상 있을 경우 해당 칸을 폭발시켜줘야 하므로 배열을 만들어

각 칸의 미친 아두이노 개수를 저장했다.

나는 문제에서 취할 수 있는 행동을 총 3가지의 함수로 나눠서 작성했다.

1. 종수 아두이노가 움직임

2. 미친 아두이노들이 움직임

3. 미친 아두이노가 여러개 있는 칸이 폭발함

 

1. 종수 아두이노가 움직이는 함수

이 함수의 로직은 매우매우매우 쉽다.

종수의 아두이노는 입력값으로 들어온 방향으로 이동한다.

이동한 칸에 뭐가 있냐에 따라 코드가 달라진다.

1) 미친 아두이노가 있음 -> 종수는 패배한다.

2) 빈칸임 -> 지도 정보를 변경해주고 종수 아두이노 위치를 업데이트한다.

 

2. 미친 아두이노들이 움직이는 함수

이 함수가 문제의 메인 로직이다.

미친 아두이노들은 동시에 움직인다는 것을 명심해야 한다.

이 부분을 신경쓰며 코드를 작성하면 크게 어렵지않다.

각 미친 아두이노들은 9가지 방향 중에 종수 아두이노와 제일 가까워지는 쪽으로 이동한다.

이 함수도 위와 마찬가지로 이동한 칸에 뭐가 있냐에 따라 코드가 달라진다.

1) 종수 아두이노가 있음 -> 종수는 패배한다.

2) 미친 아두이노가 있거나 빈칸임 -> 이동하는 위치의 지도 정보 변경하고 미친 아두이노 개수 1 증가

이후에는 현재 위치의 미친 아두이노 개수에 따라 지도 정보를 변경해주고 미친 아두이노의 개수를 1 감소시킨다.

 

3. 아두이노가 여러개 있는 칸이 폭발하는 함수

이 함수가 제일 구현하기 쉽다.

위치를 탐색하며 현재 위치에 미친 아두이노가 1개 있을 경우에는 해당 위치를 미친 아두이노 위치 큐에 추가한다.

만일, 미친 아두이노가 2개 이상이라면 현재 위치의 지도 정보를 변경하고 미친 아두이노 개수를 0으로 변경한다.

 

위의 과정들을 입력으로 주어진 종수 아두이노의 이동횟수만큼 반복한다.

만일, 중간에 종수가 패배하게 되면 반복문을 종료하고 결과를 출력한다.

이 로직들을 구현한 코드는 다음과 같다.

 

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 100

int R, C, inputJongsuMoveSize, playCnt = 0;
// 종수 아두이노의 위치와 각 좌표별 미친 아두이노 개수 저장
int jongsuArduinoX, jongsuArduinoY, crazyArduinoCnt[MAX][MAX];
// 미친 아두이노 위치 저장
queue<pair<int, int>> crazyArduino;
char MAP[MAX][MAX];
string inputJongsuMove;
// 종수 패배 여부 저장
bool lose;
int moveNum[10][2] = {{0, 0}, {1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
// 종수 아두이노 이동
bool jongsuArduinoMove(int direction)
{
    int nextX = jongsuArduinoX + moveNum[direction][0];
    int nextY = jongsuArduinoY + moveNum[direction][1];
    playCnt++;
    // 종수 아두이노와 미친 아두이노가 만나면 종수 패배
    if (MAP[nextX][nextY] == 'R')
    {
        lose = true;
        return false;
    }
    else
    {
        // 현재 위치는 빈칸으로 남김
        MAP[jongsuArduinoX][jongsuArduinoY] = '.';
        // 종수 아두이노 이동
        MAP[nextX][nextY] = 'I';
        // 종수 아두이노 위치 업데이트
        jongsuArduinoX = nextX;
        jongsuArduinoY = nextY;
        return true;
    }
}
// 미친 아두이노들 이동
bool crazyArduinoMove()
{
    while (!crazyArduino.empty())
    {
        int currentX = crazyArduino.front().first;
        int currentY = crazyArduino.front().second;
        // 미친 아두이노와 종수 아두이노간의 최소 거리,
        // 미친 아두이노가 이동하게 될 위치 저장
        int minDistance = 200, nextX, nextY;
        crazyArduino.pop();
        for (int i = 1; i < 10; i++)
        {
            int tempNextX = currentX + moveNum[i][0];
            int tempNextY = currentY + moveNum[i][1];
            int distance = abs(jongsuArduinoX - tempNextX) + abs(jongsuArduinoY - tempNextY);
            if (minDistance > distance)
            {
                minDistance = distance;
                nextX = tempNextX;
                nextY = tempNextY;
            }
        }
        // 종수 아두이노와 미친 아두이노가 만나면 종수 패배
        if (MAP[nextX][nextY] == 'I')
        {
            lose = true;
            return false;
        }
        // 이동하려는 곳에 미친 아두이노가 있거나 빈칸이면
        if (MAP[nextX][nextY] == 'R' || MAP[nextX][nextY] == '.')
        {
            // 미친 아두이노 이동
            MAP[nextX][nextY] = 'R';
            // 이동하려는 위치의 미친 아두이노 개수 1 증가
            crazyArduinoCnt[nextX][nextY]++;
        }
        // 현재 위치의 미친 아두이노가 1개 미만이라면
        if (crazyArduinoCnt[currentX][currentY] <= 1)
        {
            // 현재 위치 빈칸으로 변경
            MAP[currentX][currentY] = '.';
        }
        // 현재 위치의 미친 아두이노 개수 1 감소
        crazyArduinoCnt[currentX][currentY]--;
    }
    return true;
}
// 같은 칸에 미친 아두이노가 2개 이상 있을 시 해당 칸 폭발시킴
void explosion()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            // 현재 위치에 미친 아두이노가 1개 있다면
            if (crazyArduinoCnt[i][j] == 1)
            {
                // 미친 아두이노 위치 추가
                crazyArduino.push({i, j});
            }
            // 현재 위치에 미친 아두이노가 2개 이상 있다면
            else if (crazyArduinoCnt[i][j] >= 2)
            {
                // 현재 위치 빈칸으로 만듬
                MAP[i][j] = '.';
                // 현재 위치의 미친 아두이노 개수 0으로 변경
                crazyArduinoCnt[i][j] = 0;
            }
        }
    }
}

int main()
{
    cin >> R >> C;

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
            // 현재 위치에 미친 아두이노가 있다면
            if (MAP[i][j] == 'R')
            {
                // 미친 아두이노 위치 추가
                crazyArduino.push({i, j});
                // 현재 위치의 미친 아두이노 개수 1 증가
                crazyArduinoCnt[i][j]++;
            }
            // 현재 위치에 종수 아두이노가 있다면
            else if (MAP[i][j] == 'I')
            {
                // 위치 저장
                jongsuArduinoX = i;
                jongsuArduinoY = j;
            }
        }
    }

    cin >> inputJongsuMove;
    inputJongsuMoveSize = inputJongsuMove.size();

    for (int i = 0; i < inputJongsuMoveSize; i++)
    {
        // 이동 중간에 종수가 진다면 반복문 종료
        if (!jongsuArduinoMove(inputJongsuMove[i] - '0'))
        {
            break;
        }
        if (!crazyArduinoMove())
        {
            break;
        }
        explosion();
    }

    if (lose)
    {
        cout << "kraj " << playCnt;
    }
    else
    {
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                cout << MAP[i][j];
            }
            cout << '\n';
        }
    }

    return 0;
}