[Algorithm] Baekjoon 2933번 : 미네랄

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

2933번: 미네랄

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
struct Node
{
    int y;
    int x;
};
 
int r, c, n;
char arr[101][101] = { 0 };
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} }; // 좌, 우, 상,하
 
int throwInfo[101] = { 0 };
int visited[101][101] = { 0 };
vector<Node> prevAddedNodes;
 
 
bool cmp(const Node& a, const Node& b) // y가 클수록 땅에 가까움
{
    return a.y > b.y;
}
 
bool isGroundCluster(int startY, int startX, int mark)
{
    // 1,2,3,4 == 좌,우,상,하 표시.
 
    queue<Node> q;
    q.push({ startY,startX });
    visited[startY][startX] = mark;
    prevAddedNodes.push_back({ startY,startX });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        if (curY == r-1 || (visited[curY][curX] >= 1 && visited[curY][curX] != mark)) // 이게 가능한 이유는, 만약 낙하될 클러스터에 대한 탐색이면                                    
        {                                                                            // 이후 이 함수를 수행 안한다는게 보장되어지기 때문.
            return true;
        }
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (visited[nextY][nextX] == mark) continue; // 자기꺼면 탐색x.
            if (visited[nextY][nextX] >= 1) return true; // 자기꺼 아닌데 이미 표시되어있다면 -> 이전에 땅이랑 연결된 방향탐색노드들.
 
            if (arr[nextY][nextX] != 'x') continue; // 'x'값이여야만 함. x를 탐색하는거니까 
                                                    // 즉, 'x'면서 아직 탐색안한거
 
            visited[nextY][nextX] = mark;
            q.push({ nextY,nextX });
            prevAddedNodes.push_back({ nextY,nextX });
        }
    }
 
    return false;
}
 
void DestroyMineral(int targetY, int isRight)
{
    memset(visited, 0, sizeof(visited));
 
    if (targetY == 5)
    {
        int asfd = 0;
    }
 
    Node startNode = { -1,-1 };
 
    if (isRight == 0)
    {
        for (int i = 0; i < c; ++i)
        {
            if (arr[targetY][i] == 'x')
            {
                startNode.y = targetY;
                startNode.x = i;
                arr[targetY][i] = '.'; // 부수고
                break;
            }
        }
    }
    else
    {
        for (int i = c - 1; i >= 0; --i)
        {
            if (arr[targetY][i] == 'x')
            {
                startNode.y = targetY;
                startNode.x = i;
                arr[targetY][i] = '.'; // 부수고
                break;
            }
        }
    }
 
    if (startNode.y == -1) return; // 허공에 던진거면
 
    for (int i = 0; i < 4; ++i) // 좌,우,상,하,
    {
        if (i == isRight) continue;
 
        prevAddedNodes.clear();
 
        int startY = startNode.y + dir[i][0];
        int startX = startNode.x + dir[i][1];
 
        if (startY < 0 || startY >= r) continue;
        if (startX < 0 || startX >= c) continue;
        if (arr[startY][startX] == '.') continue;
 
        bool check = isGroundCluster(startY, startX, i + 1);
 
        if (!check) // 땅에붙어있는거 아니면 == 낙하할덩어리면 더이상 탐색 무의미.
        {
            // 땅에 가까운순으로 정렬.
            sort(prevAddedNodes.begin(), prevAddedNodes.end(), cmp);
 
            while (1)
            {
                bool isCheck = true;
 
                vector<Node> temp;
 
                for (int i = 0; i < prevAddedNodes.size(); ++i)
                {
                    int curY = prevAddedNodes[i].y;
                    int curX = prevAddedNodes[i].x;
 
                    if (curY + 1 == r || arr[curY + 1][curX] == 'x')
                    {
                        isCheck = false;
                        break;
                    }
                    else
                    {
                        arr[curY][curX] = '.';
                        arr[curY + 1][curX] = 'x';
                        temp.push_back({ curY + 1,curX }); // 변경한거 저장.
                    }
                }
 
                if (!isCheck) // 전부 한칸씩 땅으로 땡기는게 불가능하면 원상복귀
                {
                    for (int i = 0; i < temp.size(); ++i)
                    {
                        int curY = temp[i].y;
                        int curX = temp[i].x;
 
                        arr[curY][curX] = '.';
                    }
 
                    for (int i = 0; i < prevAddedNodes.size(); ++i)
                    {
                        int curY = prevAddedNodes[i].y;
                        int curX = prevAddedNodes[i].x;
 
                        arr[curY][curX] = 'x';
                    }
 
                    break;
                }
                else
                {
                    prevAddedNodes = temp;
                }
            }
 
            break;
        } 
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> throwInfo[i];
 
        DestroyMineral(r - throwInfo[i], i%2);
    }
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            printf("%c", arr[i][j]);
        }
 
        printf("\n");
    }
}
 
 

 

 

골드 1,2 BFS문제는 조건들이 많아서 코테에서 만약 IDE 못쓰게 막아놓으면 시간내에 풀지 못할 것 같다.

디버깅이 너무 오래걸린다...

 

먼저 던질 막대기의 높이에 해당하는 곳의 미네랄을 파괴한다.

왼쪽,오른쪽에 있는 사람 두명이서 번갈아면서 던지기 때문에, 왼쪽에서 던지는 경우는 해당 높이(행)에서 가장 왼쪽에 있는 미네랄을, 오른쪽에서 던지면 그 반대로 수행한다.

 

그리고 여기서 입력값으로 주어지는 높이는 배열인덱스 y와 반대라는걸 명심하자. (그래서 r에서 입력값을 빼줬다)

 

해당하는 부분의 미네랄을 파괴 후, 세 방향으로 탐색을 수행한다. 세 방향인 이유는, 왼쪽에서 던져서 파괴된 미네랄일 경우 왼쪽에 미네랄이 있을리가 없기 때문이다. (애초에 가장 왼쪽에 있는 미네랄이 파괴된 경우니까)

그러니 왼쪽에서 파괴된 경우면 위,아래,오른쪽만 탐색을 수행한다.

 

해당 방향으로의 클러스터를 탐색했을 때 처음 수행시작한 방향에 따라 값을 visited에 기록해준다. (visited는 0으로 초기화되어있다) 그리고 새롭게 탐색한 노드들을 prevAddedNodes라는 버퍼큐에 따로 보관해준다.

따로 보관하는 이유는, 낙하시켜야할 클러스터를 발견한다면 이후 낙하시키는 로직을 수행해야하기 때문에 낙하클러스터노드들을 따로 보관해야 한다.

 

그런식으로 수행하다 만약 땅을 만난다면 바로 true를 리턴하고, 탐색이 완전히 끝날때까지(큐가 비워질때까지) 땅을 만나지 못한다면 false를 리턴한다.

 

첫번째 방향검색에서 true가 리턴되었다면 (즉 땅이랑 이어진 클러스터였다면) 이어서 다른 방향도 계속 탐색한다.

탐색할 때, visited[i][j]에 1이상의 값이 기록되어있다면 이미 이전에 땅이랑 이어진 클러스터라는 뜻이므로 계속 탐색할 필요가 없다. 그러므로 바로 수행을 종료해준 후, 다음 방향탐색을 수행한다.

 

중간에 어떤 방향탐색에서 false가 리턴되었다면, 즉 땅이랑 이어지지 않은 클러스터를 찾았다면 바로 방향탐색을 종료해준다. 이 문제에서는 '특정 미네랄을 파괴함으로써 낙하할 클러스터는 반드시 1개를 넘지않는다!' 라는 가정이 있기 때문에 이러한 로직이 가능하다.

물론 특정 미네랄을 파괴했을 때 낙하할 클러스터가 없는 경우도 있다는 것을 명심하자. 무조건 낙하클러스터가 있는게아니다. 낙하 클러스터가 없는경우 어차피 다 하나의 클러스터로 이어져있는거니까 한방향의 BFS탐색만 하더라도 전부 visited에 표시가 되기 때문에 중복된 탐색을 하지 않는다.

 

낙하클러스터가 있는 경우, 방향탐색을 바로 탈출할 것이다.

그러면 현재 버퍼큐에는 낙하클러스터를 구성하는 노드들이 담겨져있다. 그러면 해당 노드들을 일단 한칸씩 땅으로 당겨보는 시도를 한다. 

당겨보는 시도란, 각 노드의 y값+1지점에 해당하는 부분이 비어있는지 체크를 하고 일단 당겨놓는다.

만약 해당지점이 범위를 벗어나거나 미네랄이라면, 해당 클러스터 노드들 전부 당기는걸 멈춘다.

 

즉, '모든 노드'들이 땅으로 1칸씩 당길 수 있어야만 낙하클러스터 자체가 땅쪽으로 1칸이동이 가능하다.

단 하나라도 이동하지 못한다면 (아마 어딘가에 걸렸다면) 더이상 이동을 못한다고 판단하고 반복문을 탈출하면 된다.

 

땅쪽으로 낙하하는 로직같은 경우는 아래와 같다.

먼저 버퍼큐의 노드들을 y값 기준으로 정렬을 해준다. 땅에 가장 가까운것부터 순차적으로 담기게 정렬해준다.

땅에 가장 가깝다는것은 y값이 가장 커야한다니까 아래처럼 sort의 cmp함수를 작성해주면 된다.

참고로 버퍼큐라고 말하긴했는데 vector다.

 

bool cmp(const Node& a, const Node& b)

{

  return a.y > b.y;

}

 

정렬된 노드들을 0번째부터 하나씩 꺼내서 y+1부분을 체크 후, 비어있으면 현재 좌표에는 '.'을, y+1부분을 'x'부분으로 표시한다. 그리고 수정한 좌표들을 또 다른 임시벡터에 보관한다.

왜냐하면 이렇게 하나씩 수정하다가 하나라도 y+1지점으로 이동을 못할 경우, 다시 원래대로 되돌려야하기 때문이다.

되돌리려 할 경우 임시벡터의 좌표에 해당하는 부분들을 전부 '.'으로, prevAddedNodes(원본)의 좌표에 해당하는 부분들을 전부 'x'로 하면 된다.

 

전부 한칸씩 당길 수 있는 경우, 수정된 좌표들에 대해서 또 한칸 씩 당기는 시도를 해야하기 때문에 임시벡터를 그대로 prevAddedNodes로 옮긴다 (prevAddedNodes = temp).

 

좀 복잡한거같긴한데, 그래도 수행속도는 잘나온다.