[코드트리] 구슬의 이동 C++

문제

https://www.codetree.ai/missions/2/problems/marble-movement?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획세우기

marble[i][0]:구슬의 번호(들어온 순서), marble[i][1]: x, marble[i][2]: y, marble[i][3]: dir, marble[i][4]: v(1초에 움직이는 양)

 

아래 과정을 time 동안 반복

1. 구슬 이동

• dx, dy이용. marble[i][4]에 들어있는 값만큼 marble[i][3] 방향으로 이동
• 범위를 벗어나면 방향을 바꾸고 다음 좌표 재설정
• 변경된 좌표 및 방향을 벡터에 갱신

2. 구슬이 k보다 많이 들어 있는 칸 찾기

3. 해당 칸에 있는 구슬 중 우선 순위가 낮은 것 지우기

• (해당 칸에 구슬이 k개 이하가 될 때까지 반복): 가장 우선순위가 낮은 값을 범위 밖의 값(x=-1, y=-1, v=100)으로 설정
• 재정렬(v가 큰 수가 뒤로 정렬되도록 했기 때문에 없앨 구슬은 뒤쪽에 정렬된다.)
• 뒤쪽에 있는 값을 pop_back으로 없애준다.

 

아래는 틀렸던 테스트 케이스가 왜 틀린 건지 보려고 구글 슬라이드로 시뮬레이션 한 것

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, t, k;

int arr[51][51];
vector<vector<int> > marble;

bool InRange(int x, int y){
    return x>=0 && x<n && y>=0 && y<n;
}

int DirConvertToInt(char dir){
    if (dir=='L') return 0;
    if (dir=='U') return 1;
    if (dir=='R') return 2;
    if (dir=='D') return 3;
    return -1;
}

// 우선순위: 속도가 빠른 구슬이 높음(같을 경우 구슬의 번호가 더 큰 구슬이 높음)
// 구슬의 번호는 입력된 순서
// 우선순위가 낮은 순서로 없앰
bool cmp(vector<int> &v1, vector<int> &v2){
    if(v1[4]==v2[4]) return v1[0]<v2[0];
    return v1[4]<v2[4];
}

void MoveMarble(){
    //L(0,-1) U(-1,0) R(0,1) D(1,0)
    int dx[4]={0, -1, 0, 1};
    int dy[4]={-1, 0, 1, 0};

    for(int i=0; i<m; ++i){
        int dir=marble[i][3];
        int move=marble[i][4];
        while (move--){
            int nx = marble[i][1]+dx[dir];
            int ny = marble[i][2]+dy[dir];
            if(!InRange(nx, ny)){
                dir= (dir+2)%4;
                nx = marble[i][1]+dx[dir];
                ny = marble[i][2]+dy[dir];
            }
            arr[marble[i][1]][marble[i][2]]--;
            marble[i][1]=nx;
            marble[i][2]=ny;
            marble[i][3]=dir;
            arr[nx][ny]++;
        }
    }
}

void RemoveMarble(int x, int y){
    // k이하가 될 때까지 우선순위에 따라 
    while (arr[x][y]>k){
        for(int i=0; i<marble.size(); i++){
            if(marble[i][1]==x && marble[i][2]==y){
                marble[i][1]=-1;
                marble[i][2]=-1;
                marble[i][4]=100; // 1<=v<=10
                arr[x][y]--;
                m--;
                break;
            }
        }
    }

    sort(marble.begin(), marble.end(), cmp);
    while(marble.size()>m){
        marble.pop_back();
    }
}

void Progress(){
    // t초 동안 반복
    while(t--){
        //1. 구슬 이동
        MoveMarble();

        //2. 구슬이 k개 이상이 칸 찾기
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                // 3. k이상이 칸에 있는 구슬 우선순위에 따라 삭제
                if(arr[i][j]>k) RemoveMarble(i, j);
            }
        }
    }
}

int main() {
    // input
    cin >> n >> m >> t >> k;
    for(int i=0; i<m; ++i){
        int r, c, v;
        char dir;
        cin >> r >> c >> dir >> v;
        marble.push_back({i, r-1, c-1, DirConvertToInt(dir), v});
        arr[r-1][c-1]=1;
    }

    sort(marble.begin(), marble.end(), cmp);
    Progress();

    // output
    cout << m << '\n';
    return 0;
}