[Algorithm] Baekjoon 16920번 : 확장 게임

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

16920번: 확장 게임

struct Node
{
    int y;
    int x;
    int range;
};
 
int n, m, p;
int pInfo[10] = { 0 };
vector<string> arr;
vector<queue<Node>> prevAddedNodes(10);
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int answerArr[10] = { 0 };
int extensionCount = 0;
 
void BFS(int playerNum)
{
    queue<Node> q;
 
    int qSize = prevAddedNodes[playerNum].size();
 
    for (int i = 0; i < qSize; ++i)
    {
        Node node = prevAddedNodes[playerNum].front();
        q.push(node);
        prevAddedNodes[playerNum].pop();
    }
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        int curRange = q.front().range;
 
        q.pop();
 
        if (curRange >= pInfo[playerNum]) continue;
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= m) continue;
            if (arr[nextY][nextX] == '#') continue;
            if (arr[nextY][nextX] >= '1' && arr[nextY][nextX] <= '9') continue;
 
            // 빈 곳
 
            q.push({ nextY,nextX,curRange + 1 });
            arr[nextY][nextX] = playerNum + '0'; // 표시하고
            prevAddedNodes[playerNum].push({ nextY,nextX,0 }); // 추가된 노드를 담는 벡터에 담아주고
            ++extensionCount; // 종료검사해야하니까 체크해주고
            answerArr[playerNum] += 1; // 정답배열에 추가해주고
 
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> p;
 
    for (int i = 1; i <= p; ++i)
    {
        cin >> pInfo[i];
    }
 
    for (int i = 0; i < n; ++i)
    {
        string temp;
        cin >> temp;
        arr.push_back(temp);
 
        for (int j = 0; j < m; ++j)
        {
            if (temp[j] >= '0' && temp[j] <= '9')
            {
                prevAddedNodes[temp[j] - '0'].push({ i,j,0 });
                answerArr[temp[j] - '0'] += 1;
            }
        }
    }
 
    while (1)
    {
        extensionCount = 0;
 
        for (int i = 1; i <= p; ++i)
        {
            BFS(i);
        }
 
        if (extensionCount == 0) break;
    }
 
    for (int i = 1; i <= p; ++i)
    {
        cout << answerArr[i] << ' ';
    }
}

문제이해를 좀 잘못해서 걸리긴했는데.. 골드2치고는 좀 쉬운문제다. 구현느낌?

혹시 나처럼 헷갈리는 사람을 위하여 미리 말하자면, 상하좌우로 정해진칸만큼 이동가능하다는것은

상 2칸, 하 2칸, 좌2칸, 우2칸 이렇게만 이동가능하다는게 아니라 그냥 아무방향으로나 정해진 범위만큼이면 아무렇게나 이동가능하다. 즉 좌2칸뿐만 아니라 좌1칸간다음 우1칸 가는것처럼 대각선 이동도 가능하다.

 

나는 이걸 이상하게 이해했었다;; 무조건 기준노드를 기준으로 각 네방향으로만 이동가능한 줄 알았다..

 

코드에 대해 간략히 설명하면 새롭게 성을 세울때마다 카운팅해주고 특정 벡터에 담아준다.

그리고 다음턴이 왔을 때 특정벡터에 담아둔 노드들만 꺼내서 큐에 넣고 또 탐색한다.

즉, 이전턴때 새롭게 추가됐던 노드들에 한해서만 이번턴에 탐색을 새롭게 수행하는 것이다.