백준 - 3025 돌던지기 (게임에서 falling sand 같은 느낌)

알고리즘문제 풀어보기/백준

백준 - 3025 돌던지기 (게임에서 falling sand 같은 느낌)

rimugiri 2024. 10. 31. 02:58

728x90

해결과정 - stack

첫번째 해결 주어진 문제대로 하나씩하니씩 전진하며 시뮬을 돌려보는 방법을 적용해보았지만 역시 시간초과가 발생했다

한턴마다 위에 적용된 예시대로 확인하며 한칸 한칸씩 이동하니 시간초과가 발생할 수 밖에 없었다.

첫번째 방식

#include<bits/stdc++.h>

#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

using namespace std;

int R, C;
vector<vector<char>> board;

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

    cout << '\n';
    return;
}

pair<int, int> find_next_pos(int r, int c) {
    //아래 확인
    int down_r = r + 1;
    
    if (board[down_r][c] == 'X') return { r, c };
    //돌일경우와 빈 공간일 경우 구분
    if (board[down_r][c] == 'O') {
        //왼쪽 우선 확인
        int left_c = c - 1;
        int right_c = c + 1;
        if (left_c >= 0 && board[r][left_c] == '.' && board[down_r][left_c] == '.') return { down_r, left_c };
        if (right_c < C && board[r][right_c] == '.' && board[down_r][right_c] == '.') return { down_r, right_c };
        return { r,c };
    }
    else {
        return { down_r, c };
    }
}

void do_simulation(int r, int c) {
    if (r == R - 1) {
        board[r][c] = 'O';
        return;
    }
    pair<int, int> next_pos = find_next_pos(r, c);

    if (next_pos.first == r && next_pos.second == c) {
        board[r][c] = 'O';
        return;
    }
    do_simulation(next_pos.first, next_pos.second);
}

void simulate(int col) {
    int start_r = 0;
    int start_c = col;

    do_simulation(start_r, start_c);    
    return;
}

int main() {
    Fast;

    cin >> R >> C;

    board.resize(R, vector<char>(C));

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

    int query;
    cin >> query;
    while (query--) {
        int input;
        cin >> input;

        int col = input - 1;

        simulate(col);
    }
    
    print();
    return 0;
}

두번째 방식은 이 코드에서 X인 벽을 각각의 열마다 저장해 둔뒤 벽에 올라가있는 돌의 개수를 세어 시간을 축약하는 방식인데 예를 들어 첫번째 방식에서는 1열에 5번째에 벽이 존재할 경우 총 5번의 과정을 거쳐야 되지만 이번 방식에서는 1번의 확인으로 이를 스킵하는 것이였다. 이 방법이 처음에는 N * 30이라고 생각하였지만 계단식으로 벽이 존재할때 큰 이슈가 된다는 것을 확인하여서 역시 시간초과가 발생하였다

두번째 방식

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>

//#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

using namespace std;

// 바닥의 위치와 쌓여있는 돌의 개수를 저장해 둔다
struct Floor {
    int position, rock_count;
    Floor(int position, int rock_count) :position(position), rock_count(rock_count) {};
    Floor() { position = 0; rock_count = 0; };

    bool operator < (const Floor& cmp) const {
        return position < cmp.position;
    }
};

int R, C;
vector<vector<char>> board;
vector<vector<Floor>> _floor;

void print() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%c", board[i][j]);
        }
        printf("\n");
    }

    printf("\n");
    return;
}

pair<int, int> find_closest_row(int r, int c) {
    // 돌을 놓을수 있는 공간을 빠르게 구한다
    int index = lower_bound(_floor[c].begin(), _floor[c].end(), Floor(r, 0)) - _floor[c].begin();

    int position = _floor[c][index].position;
    int rock_count = _floor[c][index].rock_count;

    return { position - rock_count - 1, index };
}

pair<int, int> find_next_pos(int r, int c) {
    //아래 확인
    int down_r = r + 1;

    if (board[down_r][c] == 'X') return { r, c };
    //돌일경우와 빈 공간일 경우 구분
    if (board[down_r][c] == 'O') {
        //왼쪽 우선 확인
        int left_c = c - 1;
        int right_c = c + 1;
        if (left_c >= 0 && board[r][left_c] == '.' && board[down_r][left_c] == '.') return { down_r, left_c };
        if (right_c < C && board[r][right_c] == '.' && board[down_r][right_c] == '.') return { down_r, right_c };
        return { r,c };
    }
    else {
        return { down_r, c };
    }
}

void do_simulation(int r, int c) {
    pair<int, int> res = find_closest_row(r, c);
    r = res.first;
    int index = res.second;

    if (r == R - 1) {
        board[r][c] = 'O';
        _floor[c].back().rock_count++;
        return;
    }
    pair<int, int> next_pos = find_next_pos(r, c);

    if (next_pos.first == r && next_pos.second == c) {
        board[r][c] = 'O';
        _floor[c][index].rock_count++;
        return;
    }
    do_simulation(next_pos.first, next_pos.second);
}

void simulate(int col) {
    int start_r = 0;
    int start_c = col;

    do_simulation(start_r, start_c);
    return;
}

int main() {
    //Fast;

    scanf("%d %d", &R, &C);

    board.resize(R, vector<char>(C));
    _floor.resize(C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf(" %c", &board[i][j]);
            //바닥일 경우 표시를 해둔다
            if (board[i][j] == 'X') {
                _floor[j].push_back({ i, 0 });
            }
        }
    }

    // 제일 밑을 바닥으로 취급한다
    for (int i = 0; i < C; i++) {
        _floor[i].push_back({ R, 0 });
    }

    int query;
    scanf("%d", &query);
    while (query--) {
        int input;
        scanf("%d", &input);

        int col = input - 1;

        simulate(col);
    }

    print();
    return 0;
}

마지막 방식은 그럼 어떠한 열에서 돌을 던졌을때 의 경로를 추적하면 1열에서 던졌을때 곧바로 원하는 장소에 도달할 수 있지 않나 라는 생각이였다. 이 방식은 아름다웠고 위에서 작성한 코드에서 확장하기 무척 편리하였다.

각각의 열마다 stack을 둔뒤 현재 열에서 돌을 떨어트렸을경우 발생하는 경로를 stack에 저장해 두는 것이다 그다음 나중에 다시 그 열에 돌을 던졌을 경우 stack에 저장해둔 경로를 반환하여 1열에서 던졌을때 바로 전 지점에 상수시간안에 도달할 수 있게 된다.

여기에서 한가지 다른 열에서 돌을 던져 stack에 있는 공간에 돌이 생기면 어떠게 되나 였는데 이경우는 stack에서 제거하고 그 전 경로를확인하면 된다.

최종결과

#include<bits/stdc++.h>

#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

using namespace std;

// 바닥의 위치와 쌓여있는 돌의 개수를 저장해 둔다
struct Floor {
    int position, rock_count;
    Floor(int position, int rock_count) :position(position), rock_count(rock_count) {};
    Floor() { position = 0; rock_count = 0; };
    
    bool operator < (const Floor& cmp) const{
        return position < cmp.position;
    }
};

int R, C;
vector<vector<char>> board;
vector<vector<Floor>> _floor;
vector<stack<pair<int,int>>> check_point;
void print() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }

    cout << '\n';
    return;
}

pair<int, int> find_closest_row(int r, int c) { 
    // 돌을 놓을수 있는 공간을 빠르게 구한다
    int index = lower_bound(_floor[c].begin(), _floor[c].end(), Floor(r, 0)) - _floor[c].begin();

    int position = _floor[c][index].position;
    int rock_count = _floor[c][index].rock_count;

    return { position - rock_count - 1, index };
}

pair<int, int> find_next_pos(int r, int c) {
    //아래 확인
    int down_r = r + 1;
    
    if (board[down_r][c] == 'X') return { r, c };
    //돌일경우와 빈 공간일 경우 구분
    if (board[down_r][c] == 'O') {
        //왼쪽 우선 확인
        int left_c = c - 1;
        int right_c = c + 1;
        if (left_c >= 0 && board[r][left_c] == '.' && board[down_r][left_c] == '.') return { down_r, left_c };
        if (right_c < C && board[r][right_c] == '.' && board[down_r][right_c] == '.') return { down_r, right_c };
        return { r,c };
    }
    else {
        return { down_r, c };
    }
}

void do_simulation(int r, int c , int start_c) {
    pair<int, int> res = find_closest_row(r, c);
    r = res.first;
    int index = res.second;


    if (r == R - 1) {
        board[r][c] = 'O';
        _floor[c].back().rock_count++;
        return;
    }
    pair<int, int> next_pos = find_next_pos(r, c);
    check_point[start_c].push({r, c});

    if (next_pos.first == r && next_pos.second == c) {
        board[r][c] = 'O';
        _floor[c][index].rock_count++;
        check_point[start_c].pop();
        return;
    }
    do_simulation(next_pos.first, next_pos.second, start_c);
}

void simulate(int col) {
    int start_r = 0;
    int start_c = col;

    while (!check_point[start_c].empty()) {
        pair<int, int> top = check_point[start_c].top();
        int check_r = top.first;
        int check_c = top.second;

        if (board[check_r][check_c] == '.') {
            start_r = check_r;
            start_c = check_c;
            break;
        }

        check_point[start_c].pop();
    }

    do_simulation(start_r, start_c, col);    
    return;
}

int main() {
    Fast;

    cin >> R >> C;

    board.resize(R, vector<char>(C));
    _floor.resize(C);
    check_point.resize(C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
            //바닥일 경우 표시를 해둔다
            if (board[i][j] == 'X') {
                _floor[j].push_back({ i, 0 });
            }
        }
    }

    // 제일 밑을 바닥으로 취급한다
    for (int i = 0; i < C; i++) {
        _floor[i].push_back({ R, 0 });
    }

    int query;
    cin >> query;
    while (query--) {
        int input;
        cin >> input;

        int col = input - 1;

        simulate(col);
    }
    
    print();
    return 0;
}

후기

처음에는 게임에서 개발할려고 공부한 falling sand와 유사하여 확인하였다가 나중에 이 알고리즘을 통하여 skip버튼을 만들어 모래를 던지고 skip을 눌렀을경우 빠르게 최종결과를 표시할 수 있지 않을까 라고 생각해 보았다.

728x90

저작자표시

'알고리즘문제 풀어보기 > 백준' 카테고리의 다른 글

백준 32530 - Chance! 2 (0)	2024.11.07
백준 - 9202 Boqqle <트라이 연습하기> (0)	2024.11.04
백준 - 12738 가장 긴 증가하는 부분수열 (0)	2024.10.27
백준 - 2665 미로 만들기 (0)	2024.10.24
백준-2515 전시장 (0)	2024.10.24

현재글백준 - 3025 돌던지기 (게임에서 falling sand 같은 느낌)

rimugi

코딩 정리 노트

Today :
Yesterday :

유니티 에러, 백준, Youtube Data API, 넥슨, 누적합, 해싱, poketmon, 선분교차, 다이나믹프로그래밍, #수도쿠, cmd, 크루스칼 알고리즘, 오블완, 사이클 찾기, 투포인터, 수학, 티스토리챌린지, 백트래킹, 알고리즘, unity,

rimugi