✅ 한 것들

• 백준

⚔️ 백준

2293 미네랄

#include"2933.h"
using namespace std;
typedef vector<vector<char>> vvc;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int R, C, N;
vector<int> h;
vvc cave;
vvi visited;
pii dirArr[4] = {{-1,0},{0,1},{1,0},{0,-1}};

void Output()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << cave[i][j];
        }
        cout << '\n';
    }
}

void Fall(int visit_flag, int fall_length)
{
    // 맨 아래 다음 행부터 훑으면서 visit_flag면 fall_length만큼 내리기
    for (int i = R-2; i > -1; i--)
    {
        for (int j = 0; j < C; j++)
        {
            if (visited[i][j] == visit_flag)
            {
                cave[i][j] = '.';
                cave[i+fall_length][j] = 'x';
            }
        }
    }
}

int GetFallLength(int visit_flag)
{
    int fall_length = 101;
    for (int j = 0; j < C; j++)
    {
        int temp = -1;
        for (int i = 0; i < R; i++)
        {
            // visit_flag를 만나면 temp를 초기화 (만나지 않은 건 -1)
            // visit_flag가 아닌데 temp가 초기화돼있다면 temp+1 처리.
            // temp가 0보다 크고 fall_length보다 작으면 fall_length 업뎃.
            if (visited[i][j] == visit_flag) temp = 0;
            else if (temp > -1)
            {
                temp++;
                if((i+1 >= R || (cave[i+1][j]=='x'&&visited[i+1][j]!=visit_flag))
                    && fall_length > temp)
                    fall_length = temp;
            }
            // 현재 문제 : 자기 안에서 벌어지는 1칸짜리 오인 낙하
        }
    }
    return fall_length;
}

bool isValid(int i, int j)
{
    if (0 <= i && i < R && 0 <= j && j < C
        && cave[i][j] == 'x')
    {
        return true;
    }
    else return false;
}

// 던지는 방향을 visit_flag로써 사용한다
bool isGrounded(int target, int count, int dir_idx)
{
    int visit_flag = 4 * count + dir_idx;
    bool grounded = false;

    // bfs 했는데 땅을 만나면 true, 못 만나면 false
    queue<pii> q;
    pii dir = dirArr[dir_idx];
    pii cp = { h[count] + dir.first,target + dir.second}; // check point
    // 만약 확인하는 곳이 범위를 벗어난다면 true 반환하여 그냥 지나가도록
    if (!isValid(cp.first, cp.second)) return true;
    // 이미 다른 클러스터와 연결돼있었다면 grounded 취급하고 반환
    if (4 * count <= visited[cp.first][cp.second]) return true;
    visited[cp.first][cp.second] = visit_flag;
    q.push(cp);
    while (!q.empty())
    {
        pii ij = q.front(); q.pop();

        if (ij.first == R-1) grounded = true;

        for (int i = 0; i < 4; i++)
        {
            int newi = ij.first + dirArr[i].first;
            int newj = ij.second + dirArr[i].second;
            if (isValid(newi, newj)
                && visited[newi][newj] != visit_flag)
            {
                q.push({ newi,newj });
                visited[newi][newj] = visit_flag;
            }
        }
    }

    if (grounded) return true;
    else return false;
}

void Simulate(int count)
{
    bool leftOrRight = count % 2;
    int target = -1;
    if (leftOrRight == 0)
        for (int j = 0; j < C; j++)
            if (cave[h[count]][j] == 'x')
            { 
                cave[h[count]][j] = '.';
                target = j; 
                break; 
            }
    if (leftOrRight == 1)
        for (int j = C - 1; -1 < j; j--)
            if (cave[h[count]][j] == 'x')
            { 
                cave[h[count]][j] = '.';
                target = j; 
                break; 
            }

    for (int i = 0; i < 4; i++)
        if (!isGrounded(target, count, i))
        {
            Fall(4 * count+i, GetFallLength(4 * count + i));
            break;
        }
}

void Input()
{
    cin >> R >> C;
    cave = vvc(R, vector<char>(C));
    visited = vvi(R, vector<int>(C, -1));

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> cave[i][j];

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        h.push_back(R-temp);
    }
}

void B2933::Solution()
{
    Input();
    for (int i = 0; i < N; i++) Simulate(i);
    Output();
}

사람을 질리게 만드는 악랄한 문제
자력으로 맞추긴 했다

void gravity(){
    bfs(); // 바닥 클러스터 마킹

    vector<pair<int,int>> cluster;
    for(int y=0;y<r;y++){
        for(int x=0;x<c;x++){
            if(board[y][x]=='x' && !vis[y][x]) 
                cluster.push_back({y,x}); // 공중 클러스터 수집
        }
    }

    if(cluster.empty()) return;

    // 현재 위치에서 삭제
    for(auto &pos:cluster) board[pos.Y][pos.X] = '.';

    // 떨어질 수 있는 거리 계산
    int dis = 105;
    for(auto &pos:cluster){
        int ny = pos.Y+1;
        while(ny<r && board[ny][pos.X]=='.') ny++;
        dis = min(dis, ny - pos.Y - 1); // 막히기 전까지 거리
    }

    // 아래로 dis만큼 떨어뜨리기
    for(auto &pos:cluster){
        board[pos.Y + dis][pos.X] = 'x';
    }
}

다른 사람 풀이는 더 효율적이길래 봤더니

• 바닥에 있는 클러스터만 마킹하면 됐다
• 메모리는 1만개니까 마음껏 사용해도 돼서 visited 배열 아낄 필요도 없었다
• 체크가 안된 놈들이 공중 클러스터고, 바닥 클러스터에 대해 빔 쏴서 거리 확인하면 됐다

그래도 gpt가 내 코드가 더 견고하고 실무형에 가깝다고 해주긴 함
3일 동안 끙끙댔으면서 이런 소리 하는 건 정신승리긴 함